Something i didn't know about polynomials

[-Job-]

Sometimes i like to waste my time observing the behavior of certain functions and identify any patterns. Most of the time i just look at the differences (absolute value) between two consecutive elements of a sequence of numbers and look for a pattern. If no pattern is evident i take the difference of the differences and look for a pattern again, and so on.
This creates a triangle of differences. Recently i did a program that does all of this work automatically and so i had some fun generating the triangle for various functions.
I did it for the primes and found no pattern, naturally, save for some scattered n-sized triangles of 0s, bounded by 2s, like the following:
http://www.bloo.us/temp/primes.aspx?id=0

I also tried an exponential function, 2^n and obtained a cool triangle:
http://www.bloo.us/temp/primes.aspx?id=6

But i found really interesting was the polynomial functions. Granted I'm not a mathematician, but i found the following result surprising:
- for any polynomial of the form ax^d + bx^(d-1) ... cx^0, after d+1 rows all the differences become 0. This means that the (d+1)th differences are all the same. Hard to explain, easier to look at it:
For x^2:
http://www.bloo.us/temp/primes.aspx?id=1
Differences at d+1 row are all 2

For x^3:
http://www.bloo.us/temp/primes.aspx?id=2
Differences at d+1 row are all 6

For x^4:
http://www.bloo.us/temp/primes.aspx?id=3
Differences at d+1 row are all 24

For 23x^3 + 5x^2:
http://www.bloo.us/temp/primes.aspx?id=4
Differences at d+1 row are all 138

For 6x^4 + 11x^3 + 4x^2:
http://www.bloo.us/temp/primes.aspx?id=5
Differences at d+1 row are all 144

What seems to follow is that there's no polynomial that produces all the primes. There's no polynomial that produces the first 200 primes either. Though i can, from looking at the primes' triangle see that there is a degree 2 polynomial that produces:
41 43 47 53
And another degree 2 polynomial that produces:
673 677 683 691 701
etc...
But most of it is non-polynomial. The problem is that the differences of a polynomial are either increasing or the same, there's never any zeros and the primes' triangle is filled with 0s.

I have the triangle for the first 200 primes:
http://www.bloo.us/temp/primes200.htm
It's pretty big, about 2Mb.

 

[shmoe]

For the primes, you might want to look up "Gilbraith's Conjecture". See also "Iterated absolute values of differences of consecutive primes" on Odlyzko's webpage, http://www.dtc.umn.edu/~odlyzko/doc/cnt.html

For the polynomials, if f(n) is a degree d polynomial in n, then f(n+1)-f(n) will be a degree d-1 polynomial in n. So each row of your table is generated by a polynomial of degree one smaller. Hence d iterations will lead to a row of constants, d+1 or more will get rows of zeros. There's lot's of stuff relating to this, look for "forward differences" or "difference tables" or some variations. You might find it interesting to try to predict what the last row of constants before the zeros will be just by looking at your initial polynomial. What does it depend on?

 

[-Job-]

Well, i know for x^k the last row of differences, before the zeros, is k!, but i haven't had much time to look into a generalized version. It's also interesting to know that only the d+1 numbers on the left diagonal are required to produce all the numbers in the sequence (unlike the prims). I imagine that in computer science this can be used for compression. But this isn't surprising, i remember, when i was studying interpolation and numerical methods, noticing that any polynomial generated sequence can't be compressed in less than d+1 numbers.
What about this left diagonal of d+1 numbers then? I imagine it can't possibly be polynomial itself.

Looking at Gilbreath's Conjecture, the first element of any row after the first, in the primes' triangle, clearly has to be odd, but i guess it doesn't have to be always 1.

 

[shmoe]

Well, i know for x^k the last row of differences, before the zeros, is k!, but i haven't had much time to look into a generalized version.

What about x^k+x^l where l<k? How could you get the triangle for x^k+x^l given the triangles for x^l and x^k seperately?

It's also interesting to know that only the d+1 numbers on the left diagonal are required to produce all the numbers in the sequence (unlike the prims).

Have you tried to reconstruct your polynomial given this left diagonal?

I imagine that in computer science this can be used for compression. But this isn't surprising, i remember, when i was studying interpolation and numerical methods, noticing that any polynomial generated sequence can't be compressed in less than d+1 numbers.

You can't really do any better than just storing the coefficients. "Randomish" data isn't likely to fit on a polynomial of lower degree to make compression possible.

What about this left diagonal of d+1 numbers then? I imagine it can't possibly be polynomial itself.

You may know this, but given any sequence of numbers x(1),..,x(n) you can find a degree n-1 polynomial where f(i)=x(i). So when you are saying this sequence (or others) can't be a polynomial, what do you mean exactly? Some conditions on the degree? You will be able to say something about the minimum degree required from the difference table.

 

[-Job-]

Right, i meant minimum degree, but i didn't put much thought into it. I haven't tried reconstructing the sequence from the left diagonal, but i don't see any difficulty.

 

[Mickey]

I did this exact same thing while in high school, and by an interesting coincidence, I was doing it again last night, and was going to make a post on it! Although I do it all on paper, since I have yet to learn programming skills. At the time, I wrote what my geometry teacher called "telescoping equations" for each of the degrees. So for degree 3 it's already an unwieldy

((x^3 - (x-1)^3) - ((x-1)^3 - (x-2)^3)) - (((x-1)^3 - (x-2)^3) - ((x-2)^3 - (x-3)^3)) = 6

Pretty useless after I found out the factorial rule, like you did. :)

I tried a number of methods for the prime sequence. I tried to imagine them as absolute value differences for some other number sequence, and then look for some pattern in that. For example, if you start with 1 and then add 2, and then 3, and 5, and so on, the sequence eventually starts reproducing other prime numbers. A difference table of another sequence, where x is the nth position of these primes in the prime number sequence, produces a sequence that starts with

2, 5, 10, 17, 26, 41, 58

If we start with 0, a difference table on this sequence *almost* yields the start of prime number sequence.

0
   2
2
   3
5
   5
10
   7
17
   9
26
   15
41
   17
58

If 26 were 28, it would be

0
   2
2
   3
5
   5
10
   7
17
   11
28
   13
41
   17
58

It wouldn't matter anyway, because you'd have to start with the prime number sequence in order to get the process going. Still, I thought it might be interesting to see if I could find some sort of self-similarity.

I tried to alternate signs when doing these "backwards difference tables," then taking differences of their absolute values, but that achieved no interesting result, yielding a similar randomish growth pattern of "zero triangles."

I've tried to use Excel for this, but it's not as neat. I'm interested in learning how to write some programs. Would you be willing to share some of your source code with me, Job? I am a complete beginner and don't know where to start. :shy:

 

[Mickey]

You can't really do any better than just storing the coefficients. "Randomish" data isn't likely to fit on a polynomial of lower degree to make compression possible.

My first thought was compression, too, but most number sequences I've looked at devolved into zero triangles with a chain of ones.

In other words, a whole bunch of seemingly useless ones and zeroes. Instead of compression, it'd probably find its best use in cryptography.

 

[-Job-]

The programs is an ASP.NET script written in C#. The idea is pretty simple. First you need the original sequence. For the primes, i store the elements in an array, for sequences with know generating functions i use the generating function to obtain the elements.
Once you have the original sequence you iterate through its elements and compute the differences, storing them in an array. Then you repeat this process, outputting the results as you go. Then it's just a matter of formatting the results.
The code i used is below. I didn't really bother with optimization. Hpefully it's good enough to give you an idea.

public partial class temp_primes : System.Web.UI.Page
{
    double[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291 };
    double[] ints = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 };
    int xMax = 20;
    string pyramid = "";
    int modifier = 0;
    bool UseColors = true;
    int cellWidth = 6;
    int type = 0;
    protected void Page_Load(object sender, EventArgs e)
    {
        try
        {
            type = Convert.ToInt32(Request.QueryString["id"]);
        }
        catch (Exception) { };
        switch (type)
        {
            case 0:
                Response.Write("f(x) = primes<br />");
                break;
            case 1:
                Response.Write("f(x) = x^2<br />");
                break;
            case 2:
                Response.Write("f(x) = x^3<br />");
                break;
            case 3:
                Response.Write("f(x) = x^4<br />");
                break;
            case 4:
                Response.Write("f(x) = 23x^3 + 5x^2<br />");
                break;
            case 5:
                Response.Write("f(x) = 6x^4 + 11x^3 + 4x^2<br />");
                break;
            case 6:
                Response.Write("f(x) = 2^x<br />");
                break;
            case 7:
                Response.Write("f(x) = 2^x - x^2<br />");
                break;
            case 8:
                Response.Write("f(x) = x!<br />");
                break;
            case 9:
                Response.Write("f(x) = integers<br />");
                break;
        }
    }
    private void Draw()
    {
        double[][] diffs = new double[xMax][];
        diffs[0] = new double[xMax];
        for (int i = 0; i < xMax; i++)
        {
            diffs[0][i] = f(i);
            pyramid += Normalize(diffs[0][i]);
        }
        for (int i = 0; i < diffs.Length-1; i++)
        {
            int k = i + 1;
            diffs[k] = new double[diffs[i].Length - 1];
            pyramid += "<br />" + Tab(k * cellWidth / 2);
            for (int j = 0; j < diffs[k].Length; j++)
            {
                double d = Math.Abs(diffs[i][j + 1] - diffs[i][j]);
                pyramid += Normalize(d);
                diffs[k][j] = d;
            }
        }
        Contents.Text = pyramid;
    }
    private string Normalize(double n)
    {
        string val = n.ToString();
        val = val.PadRight(cellWidth, '~');
        val = val.Replace("~", "&nbsp;");
        if (n == 0) val = Red(val);
        else if (n == 2) val = Green(val);
        return val;
    }
    private string Tab(int width)
    {
        string t = "";
        t = t.PadLeft(width, '~');
        t = t.Replace("~", "&nbsp;");
        return t;
    }
    private string Red(string val)
    {
        if (UseColors) return "<span style=\"color:red;font-weight:bold;\">" + val + "</span>";
        else return val;
    }
    private string Green(string val)
    {
        if (UseColors) return "<span style=\"color:green;font-weight:bold;\">" + val + "</span>";
        else return val;
    }
    private double f(int x)
    {
        switch (type)
        {
            case 0:
                return primes[x];
            case 1:
                return Math.Pow(x, 2);
            case 2:
                return Math.Pow(x, 3);
            case 3:
                return Math.Pow(x, 4);
            case 4:
                return 23 * Math.Pow(x, 3) + 5 * Math.Pow(x, 2);
            case 5:
                return 6 * Math.Pow(x, 4) + 11 * Math.Pow(x, 2) + 4 * Math.Pow(x, 2);
            case 6:
                return Math.Pow(2, x);
            case 7:
                return Math.Pow(2, x) - Math.Pow(x, 2);
            case 8:
                return factorial(x);
            case 9:
                return ints[x];
            default: return 0;
        }
    }
    private double factorial(int n){
        double f = 1;
        while (n > 1)
        {
            f *= n;
            n--;
        }
        return f;
    }
    protected override void Render(HtmlTextWriter writer)
    {
        Draw();
        base.Render(writer);
    }
}

 

[Mickey]

Thank you very much!