Professional Help Needed-Elementary Number Theory

[gspeagle]

Professional Help Needed--Elementary Number Theory

I will preface this by saying that I have no formal training in Mathematics. I've taken Calc 1 and a couple of Symbolic Logic classes. Forgive me if I butchered any terminology. However, this has been bugging me for a while, and I would like to know if anyone knows anything about this.

There seems to be a predictable pattern in the gaps between successive terms in series with prime exponents. This has been known for x^2 for a long time.


x^1== +1
x^2 == 2x+1

x^3 == [(x^2+x)(3)] +1

1+ (1^2+1) (3) +1 = 8
8 + (2^2+2) (3) +1 = 27
27 + (3^2+3) (3) +1= 64 ...

x^5== [(x^2+x)(x^2+x+1)(5)]+1

1+[(1^2+1)(1^2+1+1)(5)]+1=32
32 + (2^2+2)(2^2+2+1)(5)+1=243
243+(3^2+3)(3^2+3+1)(5)+1=1024...


x^7 = {(x^2 + x) (x^2 + x + 1)^2 (7)} + 1

x^11 = {(x^2 + x) (x^2 + x +1) ((x^2 + x)^2 + (x^2 + x + 1)^3) (11)} + 1


x^13 = {(x^2 + x) (x^2 + x + 1)^2 (2 (x^2 + x)^2 + (x^2 + x + 1)^3) (13)} + 1

I have Mathematica notebooks with the computations for x^7,x^11, and x^13, verifying this up to x=100 and each series gap between successive members follows the pattern. However at x^17, I ran out of steam and cognitive resources. Prime factoring the [[gap term] -1] is how I started looking at the other series, and there is some frustratingly periodic behavior in the prime factors. Twin prime exponents are also connected in some way, but I cannot figure it out.

I have no idea what this means, if anything at all.

 

[ramsey2879]

I will preface this by saying that I have no formal training in Mathematics. I've taken Calc 1 and a couple of Symbolic Logic classes. Forgive me if I butchered any terminology. However, this has been bugging me for a while, and I would like to know if anyone knows anything about this.

There seems to be a predictable pattern in the gaps between successive terms in series with prime exponents. This has been known for x^2 for a long time.x^1== +1
x^2 == 2x+1

x^3 == [(x^2+x)(3)] +1

1+ (1^2+1) (3) +1 = 8
8 + (2^2+2) (3) +1 = 27
27 + (3^2+3) (3) +1= 64 ...

x^5== [(x^2+x)(x^2+x+1)(5)]+1

1+[(1^2+1)(1^2+1+1)(5)]+1=32
32 + (2^2+2)(2^2+2+1)(5)+1=243
243+(3^2+3)(3^2+3+1)(5)+1=1024...x^7 = {(x^2 + x) (x^2 + x + 1)^2 (7)} + 1

x^11 = {(x^2 + x) (x^2 + x +1) ((x^2 + x)^2 + (x^2 + x + 1)^3) (11)} + 1x^13 = {(x^2 + x) (x^2 + x + 1)^2 (2 (x^2 + x)^2 + (x^2 + x + 1)^3) (13)} + 1

I have Mathematica notebooks with the computations for x^7,x^11, and x^13, verifying this up to x=100 and each series gap between successive members follows the pattern. However at x^17, I ran out of steam and cognitive resources. Prime factoring the [[gap term] -1] is how I started looking at the other series, and there is some frustratingly periodic behavior in the prime factors. Twin prime exponents are also connected in some way, but I cannot figure it out.

I have no idea what this means, if anything at all.

Your discovery is based upon the known fact that the coefficients for the binomial (x+1) raised to a prime power P are each divisible by P except the coefficients of x^p and 1. Try searching for the terms "binomial coefficients" and "primes" to see how to prove this.

P.S. you said the verified your expressions in x by checking individual values in x, say from 1 to 100. The correct use of power of algebra would be to multiply the products, group like terms, and to verify the resulting expression using Pascal's Triangle. I would think this could be done using Mathematica functions. Try asking for help with this in a Mathematica User's group. This would save a lot of computation.

P.P.S. It appears that you meant to use == instead of = for the expressions for x^7, x^11 and x^13. Your Terminology is unclear. The expressions on the right seem to be (x+1)^n - x^n. In other words you meant to write: (x+1)^n mod x^n == the expression on the right.

 

[gspeagle]

I'm a little lost when it comes to the binomial coefficients. But there are also some other interesting characteristics of the gap term. The sum of the even numbers (x^2+x) and the partial sums of the octahedral numbers also shows up as factors in sequence. [PLAIN]http://https://oeis.org/A006325.[/PLAIN]

Is that the issue then? Does the binomial theorem explain this and if I understood the binomial theorem would I understand why x^p series behave this way?

 

[gspeagle]

I emailed a Mathematician who started a relatively successful website devoted to Math and Integers about this, and this was his reply. I am not sure if this explains my original question, as Pascal's Triangle would account for the P factor in the gap, but the P is only one part of the functions.

I am also a little confused on the Maple program that was used, as you can see below, the outputs the Mathematician returned to me use composite exponents that increase (x^6,x^5, etc) whereas the initial functions only use x^2 and x^3. Can someone explain what he is talking about?


Dear Gordon, Thanks for that message.
What makes this work is an old theorem of
Lucas, that says that if p is a prime, every term in
the p-th row of Pascal's triangle (except the 1's at the ends) is
divisible by p.

To do this algebraically, - which is what you are doing -
we can take (x+1)^p, subtract x^p and 1, and then
what is left will be divisible by p and we can try to
factor it.

Here I will do that in Maple:

> f:=n->lprint(factor((x+1)^n-x^n-1));

> f(2);
2*x

> f(3);
3*x*(1+x)

> f(5);
5*x*(1+x)*(x^2+x+1)

> f(7);
7*x*(1+x)*(x^2+x+1)^2

> f(11);
11*x*(1+x)*(x^2+x+1)*(x^6+3*x^5+7*x^4+9*x^3+7*x^2+3*x+1)
> f(13);
13*x*(1+x)*(x^6+3*x^5+8*x^4+11*x^3+8*x^2+3*x+1)*(x^2+x+1)^2
> f(17);
17*x*(1+x)*(x^2+x+1)*(x^12+6*x^11+26*x^10+75*x^9+156*x^8+240*x^7+277*x^6+240*x^5+156*x^4+75*x^3+26*x^2+6*x+1)

> f(19);
19*x*(1+x)*(x^12+6*x^11+28*x^10+85*x^9+184*x^8+292*x^7+341*x^6+292*x^5+184*x^4+85*x^3+28*x^2+6*x+1)*(x^2+x+1)^2

> f(23);
23*x*(1+x)*(x^2+x+1)*(x^18+9*x^17+57*x^16+252*x^15+836*x^14+2156*x^13+4423*x^12+7324*x^11+9880*x^10+10911*x^9+9880*x^8+7324*x^7+4423*x^6+2156*x^5+836*x^4+252*x^3+57*x^2+9*x+1)

Further simplifications get trickier, as you noticed.

Do you know the book "Concrete Mathematics" by Graham, Knuth et al.? The discussion of Pascal's triangle there
and of the properties of binomial coefficients are relevant. It is also
great fun to read.

Best regards


My reply:

Dear XXXX,

Thanks for your prompt and thoughtful reply. I will look into the book, it sounds very interesting. I was looking over the Maple outputs, and comparing it to the initials functions to see where they went wrong, because there seemed to be a discrepancy after x^7. I know you are probably busy, but I can't figure out why the Maple output has x^n (n from 1 to 6), when the erroneous function is merely squares and cubes.




x^11 = {(x^2 + x) (x^2 + x +1) ((x^2 + x)^2 + (x^2 + x + 1)^3) (11)} + 1


> f(11);
11*x*(1+x)*(x^2+x+1)*(x^6+3*x^5+7*x^4+9*x^3+7*x^2+3*x+1)

Thanks,

Gordon

I am just getting more confused the more people I ask.

 

[ramsey2879]

I emailed a Mathematician who started a relatively successful website devoted to Math and Integers about this, and this was his reply. I am not sure if this explains my original question, as Pascal's Triangle would account for the P factor in the gap, but the P is only one part of the functions.

I am also a little confused on the Maple program that was used, as you can see below, the outputs the Mathematician returned to me use composite exponents that increase (x^6,x^5, etc) whereas the initial functions only use x^2 and x^3. Can someone explain what he is talking about?


Dear Gordon, Thanks for that message.
What makes this work is an old theorem of
Lucas, that says that if p is a prime, every term in
the p-th row of Pascal's triangle (except the 1's at the ends) is
divisible by p.

To do this algebraically, - which is what you are doing -
we can take (x+1)^p, subtract x^p and 1, and then
what is left will be divisible by p and we can try to
factor it.

Here I will do that in Maple:

> f:=n->lprint(factor((x+1)^n-x^n-1));

> f(2);
2*x

> f(3);
3*x*(1+x)

> f(5);
5*x*(1+x)*(x^2+x+1)

> f(7);
7*x*(1+x)*(x^2+x+1)^2

> f(11);
11*x*(1+x)*(x^2+x+1)*(x^6+3*x^5+7*x^4+9*x^3+7*x^2+3*x+1)
> f(13);
13*x*(1+x)*(x^6+3*x^5+8*x^4+11*x^3+8*x^2+3*x+1)*(x^2+x+1)^2
> f(17);
17*x*(1+x)*(x^2+x+1)*(x^12+6*x^11+26*x^10+75*x^9+156*x^8+240*x^7+277*x^6+240*x^5+156*x^4+75*x^3+26*x^2+6*x+1)

> f(19);
19*x*(1+x)*(x^12+6*x^11+28*x^10+85*x^9+184*x^8+292*x^7+341*x^6+292*x^5+184*x^4+85*x^3+28*x^2+6*x+1)*(x^2+x+1)^2

> f(23);
23*x*(1+x)*(x^2+x+1)*(x^18+9*x^17+57*x^16+252*x^15+836*x^14+2156*x^13+4423*x^12+7324*x^11+9880*x^10+10911*x^9+9880*x^8+7324*x^7+4423*x^6+2156*x^5+836*x^4+252*x^3+57*x^2+9*x+1)

Further simplifications get trickier, as you noticed.


Thanks for your prompt and thoughtful reply. I will look into the book, it sounds very interesting. I was looking over the Maple outputs, and comparing it to the initials functions to see where they went wrong, because there seemed to be a discrepancy after x^7. I know you are probably busy, but I can't figure out why the Maple output has x^n (n from 1 to 6), when the erroneous function is merely squares and cubes.


I am just getting more confused the more people I ask.

Keep at it, eventually everything will become clear. Based upon your work thus far, your not too far from an understanding of this topic. The maple program is somewhat like Mathematica. Basically it defines a function f(n) as equal to the expansion of (x+1)^n - x^n -1 in the format of a product of polynominal factors and P*x. The reason you see terms such as x^6 ... where you have merely squares and cubes is that you had the expression in a different format. You will only see a term such as x^6 where the n in f(n) is greater than 6, so there is no contradiction.

 

[Anti-Crackpot]

It's not just Pascal's Triangle that evidences such periodic behavior modulo p. All manner of recursively defined triangles demonstrate such behavior, from the Stirling 1 and 2 Triangles to the Eulerian Triangle to the Bernoulli Triangle and beyond.

I don't know the theorem that would apply, but the patterns are more than apparent with a little trial and error.

- AC

P.S. Ramsey 2879, are you familiar with a general theorem that generalizes Lucas' therorem re: Pascal's Triangle to other recursively defined triangles?

 

[Mandlebra]

It's not just Pascal's Triangle that evidences such periodic behavior modulo p. All manner of recursively defined triangles demonstrate such behavior, from the Stirling 1 and 2 Triangles to the Eulerian Triangle to the Bernoulli Triangle and beyond.

I don't know the theorem that would apply, but the patterns are more than apparent with a little trial and error.

- AC

P.S. Ramsey 2879, are you familiar with a general theorem that generalizes Lucas' therorem re: Pascal's Triangle to other recursively defined triangles?

Is it really ALL? That makes this far more interesting. Mind linking a paper or something?

 

[Anti-Crackpot]

Is it really ALL? That makes this far more interesting. Mind linking a paper or something?

Mandelbra,

Unfortunately, I have no paper to link to, and by no means is that failing for a lack of searching; but here's a little example of what I mean from the 29th row of the Eulerian Triangle (data courtesy of OEIS). Check any of these values modulo 29 and you'll get the same answer: 1 (mod 29)

435 1
436 536870882
437 68614271237958
438 286171698369607914
439 177647455673002199595
440 31382819428102862274060
441 2194392886612867977544380
442 73424846658979203874373100
443 1323982746583831999659021945
444 13919693671791536153349072870
445 90061513941680102366609674650
446 372321031278485080481062180110
447 1009202977757986820086345359195
448 1824120537458837340596389252680
449 2219711218428375098854998661320
450 1824120537458837340596389252680
451 1009202977757986820086345359195
452 372321031278485080481062180110
453 90061513941680102366609674650
454 13919693671791536153349072870
455 1323982746583831999659021945
456 73424846658979203874373100
457 2194392886612867977544380
458 31382819428102862274060
459 177647455673002199595
460 286171698369607914
461 68614271237958
462 536870882
463 1
https://oeis.org/A173018

The no-brainer explanation I can't seem to find anywhere almost certainly has to do with the cyclical group nature of the primes...

- AC

 

[gspeagle]

Quick question: Why would anyone have the desire prove anything after Godel?