Mathematics desk
< August 9	<< Jul \| August \| Sep >>	August 11 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 10

Finding rational coefficients of a cubic polynomial that fits 4 data points that have been floored to an integer

I have 4 data points:

(204, 5422892)
(205, 5722486)
(207, 6343357)
(213, 8386502)

I have information that these data points were generated with a cubic polynomial

y = ax ^ 3 + bx ^ 2 + cx + d

with a, b, c, and d being ~~positive~~ rational (but not necessarily integral) coefficients, and with the resulting y values being floats that were floored to an integer (the x values are known to be true integers, not floored floats). I also have information that the coefficients are relatively "nice", "simple", or "short" numbers with only a few digits like 50 or 1/2 rather than anything that is a long string of many digits.

I need to determine what those coefficients are. I tried submitting the query

"find cubic polynomial that fits (204, 5422892), (205, 5722486), (207, 6343357), (213, 8386502)"

to Wolfram Alpha, but Wolfram Alpha gives me the answer

(589/36) x ^ 3 - (116363/18) x ^ 2 + (10691263/12) x - 46197659

which has coefficients that are rational but are ~~not positive and~~ not "nice" (in the sense used above). I think the difficulty is that Wolfram Alpha is using Lagrange interpolation to try to find a cubic polynomial that is an absolute exact fit to the given data points, but there is actually flooring to an integer being applied to the y values.

So can anyone help me...

(1) find the coefficients for this specific case of the 4 data points given above?

(2) show me how to, in general, given any 4 data points that are known to be generated with a cubic polynomial with ~~positive~~ rational coefficients with the y values then floored to an integer, find those coefficients? (I am aware of Lagrange interpolation, but I think that is what Wolfram Alpha is doing above and is what is giving wrong results due to not being able to take into account flooring.)

—SeekingAnswers (reply) 11:49, 10 August 2023 (UTC)[reply]

(Update to original post: I am virtually certain that the y values are being floored rather than having any other type of rounding.) —SeekingAnswers (reply) 17:46, 10 August 2023 (UTC)[reply]

I've actually solved this kind of thing, but the method I used isn't simple and I don't guarantee it's the most practical. What you've got is a system of linear inequalities starting with 5422892-1/2 ≤ 204³a + 204² + 204c + d ≤ 5422892+1/2 (assuming simple rounding is used). This is a total of 8 inequalities in 4 unknown, and it produces a 4-dimensional polytope in (a, b, c, d)-space. If there happens to be an integer point in it, and if you can find it, or them if there are more than one, then you're done. Trying to find an integer solution changes the problem from an example of linear programming to an example of integer programming. If there is no integer solution (and it's not hard to see that there isn't in this case), then you can try different "nice" denominators, for example solve with a=A/2, b=B/2, c=C/2, d=D/2 where A, B, C, D are integers. If you get to a=A/36, b=B/36, c=C/36, d=D/36 you can stop because that's just the Lagrange solution. I'd suggest as a first step, round the Lagrange coeffs to the nearest integer, then subtract the values of that polynomial from the points to get smaller, more tractable numbers. You can add the rounded Lagrange coeffs back in when you're done to get a solution to the original problem. Also offset the x values by 204 so you x values of 0, 1, 3, 9, also to make the numbers smaller and more tractable. To put the answer in the original range change x to (x-204). I don't know what's publicly available in terms of IP solvers, but if you state the problem as a system of inequalities you might find something to do most of the actual work for you. --RDBury (talk) 16:22, 10 August 2023 (UTC)[reply]

PS. Less elegant but perhaps easier to implement, for a given denominator N there are about N⁴ possible combinations of values you can get for the values of your polynomial at the four points. For N≤36 that's low enough to use a brute force search. For each set of values find the Legrange polynomial that fits those values, if the denominators you get are factors of N then you have a solution. With N=32 that's about 1,000,000 combinations to try, and it probably wouldn't take a computer too long to check them all. A lot of the work, for example finding the Lagrange basis, only has to be done once. --RDBury (talk) 16:42, 10 August 2023 (UTC)[reply]

A cubic polynomial that can give rise – whether with rounding to the nearest integer or with rounding down – to the given data set cannot have only non-negative coefficients. The constant coefficient of any such polynomial is necessarily less than −45 600 000, while that of

x

² is less than −6 400. --Lambiam 20:20, 10 August 2023 (UTC)[reply]

Yes, the problem would have to be reworked a bit to fit the usual paradigm, but there are standard techniques for doing this. Convert each each inequality to an equality with a slack variable. For example -130 ≤ x ≤ 50 becomes -130+s = x, x+t = 50, s, t ≥ 0. Since x has unrestricted sign it can be eliminated to give s+t=180, s, t ≥ 0. Once you have a solution you'd have to use back substitution to get the original variables. I would think a good LP/IP solver would do this kind of thing for you. Btw, it seems modern spreadsheet programs have solvers built in, but I've never tried using them. There are (of course) YouTube tutorials for using them. --RDBury (talk) 23:45, 10 August 2023 (UTC)[reply]

Hmm, okay, I see the problem. The context is that I am trying to reverse-engineer the behavior of some software. Related parts of the software that I have been able to reverse-engineer all use cubic polynomials with positive rational "nice" (in the sense given above) coefficients and then apply flooring, so I assumed it was true of this part as well, but it looks like at least the "positive" part of that pattern is being broken. —SeekingAnswers (reply) 01:56, 11 August 2023 (UTC)[reply]