A new Strong Law of Small Numbers example

[cheesehead]

From the NMBRTHRY mailing list comes a recent example of the first Strong Law of Small Numbers (http://mathworld.wolfram.com/StrongL...llNumbers.html).

Last Sunday:

A surprising conjecture: n=x^2+T_y+F_m

Sunday, December 21, 2008 12:28 PM

From:
"Zhi-Wei SUN" <zwsun@nju.edu.cn>


Dear number theorists,

Recall that triangular numbers have the form T_n=n(n+1)/2
(n=0,1,2,...), and the Fibonacci numbers are given by

F_0=0, F_1=1, and F_{n+1}=F_n+F_{n-1} (n=1,2,3,...).

Here I pose the following somewhat suprising conjecture:

Conjecture (Z. W. Sun, 2008) Each natural number can be written as the
sum of a square, a triangular number and a Fibonacci number.
Furthermore, c= lim inf_n r(n)/log n is a positive constant, where
r(n) denotes the number of ways to write n in the form x^2+T_y+F_m
with x,y,m non-negative integers.

I have verified the conjecture for all natural numbers not exceeding
2,300,000. By my computation, c should be smaller than 2 and probably 0<c<1.
I have calculated r(n)/log n for n between 20,000,001 and 20,000,500;
most of the values are greater than 1 and smaller than 4.

It's not very clear why the conjecture may hold. Note that
2^{m/2}-1\le F_m<2^m and |{y\ge 0: T_y\le n}| is about sqrt{2n}. Also,
{T_y: y=0,1,2,...}
contains a complete system of residues modulo any power of two.
[Moreover, I and my student W. Zhang [arXiv:0812.3089] recently showed
that
for any given positive integer k, the set {binomial coeff. C(n,k):
n=0,1,2,...} contains a complete system of residues modulo any powers
of two, i.e., it is
a dense subset of the ring Z_2of 2-adic integers.]

Compared with the representation function for Goldbach's conjecture,
and the representation function for my conjecture on sums of primes and
triangular numbers
[arXiv:0803.3737], the above representation function r(n) grows much
slower! It seems that the above conjecture is the first example for
representation of all natural
numbers with the representation function growing so slow. Thus, in my
opinion, if the above conjecture holds, its proof would be very difficult.

Any comments are welcome!

Sincerely,

Zhi-Wei Sun (Nanjing University, China)
http://math.nju.edu.cn/~zwsun

"all natural numbers not exceeding 2,300,000" -- pretty good, but the next day brought:

From:
"Zhi-Wei SUN" <zwsun@nju.edu.cn>


Dear all,

Though I verified my incredible conjecture on n=x^2+T_y+F_m for n not
more than 2,300,000,
Dr. Douglas McNeil from University of London has found counter-examples
via an efficient program:
The smallest counter-example is n= 3,970,902, another large
counter-example is 776,218,485.

I also proposed a variant of my conjecture: n=T_x+T_y+F_m. Yet, McNeil
found counter-examples for this variant too:
The first two counter-examples are 2,892,173 and 10,991,572; large
counterexamples include 96,799,987 and 901,415,393.

I'm sorry that I raised a wrong conjecture to you. Perhaps the only
positive thing is that it provides a very good example
for R.K. Guy's Strong Law of Small Numbers.

Merry Christmas!

Zhi-Wei Sun

- - -

From:
"Giovanni Resta" <g.resta@iit.cnr.it>


Zhi-Wei SUN wrote:
> Dear number theorists,
>
> Recall that triangular numbers have the form T_n=n(n+1)/2
> (n=0,1,2,...), and the Fibonacci numbers are given by
>
> F_0=0, F_1=1, and F_{n+1}=F_n+F_{n-1} (n=1,2,3,...).
>
> Here I pose the following somewhat suprising conjecture:
>
> Conjecture (Z. W. Sun, 2008) Each natural number can be written as the
> sum of a square, a triangular number and a Fibonacci number.
> Furthermore, c= lim inf_n r(n)/log n is a positive constant, where
> r(n) denotes the number of ways to write n in the form x^2+T_y+F_m
> with x,y,m non-negative integers.

It seems to me that the number 3,970,902 is the fist one which cannot be
expressed in that form.
I've checked only up to 20,000,000 without finding any other such
number (I've had just a couple of hours because I'm leaving for
the holidays right now.)

Giovanni Resta

- - -

From:
"Kurt Foster" <drsardonicus@earthlink.net>


Based on Zhi-Wei Sun's statement in the original post, that

> It's not very clear why the conjecture may hold.

I decided to try to push the numerical search a bit further to see if
a counterexample (non-representable n) turned up. The following
considerations indicated a possibly practical approach:

n = x^2 + y*(y+1)/2 + F_m if and only if

8*n+1 = 8*x^2 + (2*y+1)^2 + 8*F_m, if and only if

8*n + 1 - 8*F_m = 8*x^2 + (2*y+1)^2 for some m >= 0.

Now if M == 1 (mod 8), (e.g. M = 8*n + 1 - 8*F_m), then

M = 8*x^2 + (2*y+1)^2 if and only if the exact prime-power exponent of
each prime p == 5 or 7 (mod 8) which divides M is even.

I wrote a Pari-GP script to implement these criteria, and let it
crunch away. Of course, it's entirely possible my script is writ
wrong, but up to the search limit 40000000 (4 x 10^7), it produced two
candidate non-representable n,

n = 3970902

and

n = 39022919

- - -

From:
"Bjorn Poonen" <poonen@math.mit.edu>

Dear Zhi-Wei Sun:

Since the number of integers up to B of the form x^2+T_y
is about a constant times B/sqrt(log B),
heuristics predict that there should be infinitely many counterexamples
to your conjecture.

If I'm not mistaken, the first one is 3970902.

Bjorn Poonen

[CRGreathouse]

Well, so much for sums of thin sequences representing all integers!

Kind of makes me wish I'd pushed ahead to find the counterexample myself.

[R. Gerbicz]

All counter example for the original conjecture up to 2^33 are:

Counter-example=3970902
Counter-example=39022919
Counter-example=102132857
Counter-example=110468517
Counter-example=368495972
Counter-example=391099413
Counter-example=395147912
Counter-example=421129348
Counter-example=452808398
Counter-example=776218485
Counter-example=1005771844
Counter-example=1485470432
Counter-example=3038310485
Counter-example=3263773338
Counter-example=3485976107
Counter-example=3640901241
Counter-example=3758331463
Counter-example=3784200441
Counter-example=3944795435
Counter-example=4014507719
Counter-example=4277741986
Counter-example=4397438442
Counter-example=4542739955
Counter-example=4757066466
Counter-example=5167438708
Counter-example=7130095749
Counter-example=7213669167
Counter-example=7424527675
Counter-example=7696559526
Counter-example=8309766941
Counter-example=8462583631

[cheesehead]

Originally Posted by CRGreathouse

Well, so much for sums of thin sequences representing all integers!

Not so fast ...

Zhi-Wei Sun isn't easily discouraged.

From the NMBRTHRY mailing list comes:

A promising conjecture: n=p+F_s+F_t

Tuesday, December 23, 2008 7:57 AM
From: "Zhi-Wei SUN" <zwsun@nju.edu.cn>
To: undisclosed-recipients

Dear number theorists,

Let {F_n} be the Fibonacci sequence given by

F_0=0, F_1=1, and F_{n+1}=F_n+F_{n-1} (n=1,2,3,...).

I have the following very promising conjecture.

CONJECTURE [Sun, Dec. 23, 2008]. Each integer n>4 can be written as the sum of an odd prime and two positive Fibonacci numbers.

I have verified the conjecture for n not exceeding 10^8. Note that 18484776 cannot be written as the sum of a prime p=1(mod 3) and two Fibonacci numbers, and 11095254 cannot be represented as the sum of a prime p=1(mod 4) and two Fibonacci numbers.

Now I provide certain evidence to support the above conjecture.

(1) The number of triples <p,s,t> with p a prime not exceeding n and F_s,F_t<n is about cn*log n, where c is a positive constant.

(2) In 1971 R. Crocker proved that there are infinitely many positive odd integers which cannot be written as the sum of a prime and at most two powers of two. [Probably any odd integer n>2 is the sum of a prime and at most three powers of two.] However, below a given n>4 there are more Fibonacci numbers than powers of two. Also, Crocker's trick involves some very special properties of powers of two and it does not work for Fibonacci numbers.

This time I'm very confident that the conjecture holds. Any comments are welcome!


Merry Christmas!

Zhi-Wei Sun
http://math.nju.edu.cn/~zwsun

followed by:

A summary concerning my conjecture: n=p+F_s+F_t

Thursday, December 25, 2008 12:22 AM
From: "Zhi-Wei SUN" <zwsun@nju.edu.cn>
To: undisclosed-recipients

Dear number theorists,

Here I summarize the recent developments concerning my conjecture on sums of a prime and two Fibonacci numbers.

In the evening of Dec. 23, 2008, I formulated the following stronger version of the conjecture and verified it up to 3*10^7.

CONJECTURE. Any integer n>4 can be written as the sum of an odd prime, an ODD Fibonacci number and a positive Fibonacci number.

Later I informed this to some authors of this mailing list including Prof. Douglas McNeil (London) and Bjorn Poonen (MIT). My former student Song Guo and Prof. McNeil have verified my above conjecture up to 4*10^8 and 2*10^9 respectively, and found NO counterexamples. McNeil told me that he would like to push the verification to 10^10.

On Dec. 23, I could not find an integer 4<n<3*10^7 not representable as the sum of a prime p=5(mod 6) and two Fibonacci numbers. Prof. Bjorn Poonen told me that by a heuristic argument there should be infinitely many positive integers not in the form p+F_s+F_t if we require that the prime p lies in a fixed residue class with modulus greater than two.
McNeil made a computer search to find integers n>4 not representable as the sum of a prime p=5(mod 6) and two Fibonacci numbers; he found two such numbers below 2*10^9: 857530546 and 278749244.


Sincerely,

Zhi-Wei Sun
http://math.nju.edu.cn/~zwsun

Originally Posted by CRGreathouse

Kind of makes me wish I'd pushed ahead to find the counterexample myself.

The clock is running ...

[CRGreathouse]

Originally Posted by cheesehead

The clock is running ...

I checked his earlier version of this conjecture (weaker, so I'm searching for a stronger counterexample) up to 2.6 x 10^10; I'm in progress for a verification to 6e10. Nothing yet.

[R. Gerbicz]

Originally Posted by cheesehead

Not so fast ...

Zhi-Wei Sun isn't easily discouraged.

From the NMBRTHRY mailing list comes:

followed by:




The clock is running ...

It looks like he has got at least one cojecture/day.

[CRGreathouse]

Originally Posted by R. Gerbicz

It looks like he has got at least one cojecture/day.

I love when he (rarely) adds timestamps in addition to datastamps to his conjectures. Who else...

He's now offering Erdős-style prizes for proofs or counterexamples:
http://listserv.nodak.edu/cgi-bin/wa...0&F=&S=&P=1395

Conjecture 1 seems considerably harder than the strong Goldbach conjecture, so I think his money is safe. The conjecture is almost certainly true.

Conjecture 2 deals with a thin sequence (O(n log n) sums up to n), but it's thicker than Crocker's 1971 p + 2^a + 2^b sequence, so it may hold.

Conjecture 3's strong form is thinner than Crocker's sequence (the Pell numbers vary as (1 + sqrt(2))^n, with 1 + sqrt(2) = 2.414... > 2) and so a failure wouldn't be surprising. But the weak form allows negative numbers, so it seems almost sure to hold.

Does anyone have thoughts on these, especially the weak form of Conjecture 3? Breaking it into classes:
1. Sum of an odd prime and two positive Pell numbers -- the strong form has only this form.
2. Sum of an odd prime, and the positive sum of two Pell numbers, one positive and one nonpositive.
3. Sum of an odd prime, and the nonpositive sum of two Pell numbers.

Given a number n, it's easy to check if it has a form in class 1 or 2. But how do you rule out the possibility that it's in class 3? Choosing arbitrarily large (in absolute value) negative Pell numbers is allowed, so how could a purported counterexample be checked?

Further, there should be something like O((log n)^2) numbers between -n and 0 that are the sum of two Pell numbers, so the 'chance' that a number will have the form of such a negative number plus a prime is large, as log^2 n * n/log n >> n.

[cheesehead]

Sun now has a website for his stuff:

"Mixed Sums of Primes and Other Terms"

http://math.nju.edu.cn/~zwsun/MSPT.htm

established on Groundhog Day, appropriately enough (for those who've seen the movie).

(and I was prime-numbered visitor "00000353" -- Is there a visitor-counter that doesn't display leading zeros?)