[seqfan] Re: An arithmetic conjecture

[David Wilson]

OK, here goes.

Warning: This discussion will involve handwaving, blind-eye turning and 
under-the-rug sweeping.


Lesson 1.  Expected intersections

Let a be an increasing integer sequence (I'm sweeping the problem of less 
kindly sequences under the rug for the moment).

Let a be asymptotic to real function f, that is lim n -> inf a(n)/f(n) = 1 
(which we abbreviate a ~ f).

For large n, we have a(n) approximately equals f(n), that is a(n) ~ f(n), in 
the relative sense.

This implies that for large n, a(f^-1(n)) ~= f(f^-1(n)) = n. So n is more or 
less the f^-1(n)th element of a.

Since a is increasing, we conclude that there are about f^-1(n) elements of 
a that are <= n.

This means that the density of a near n is about d_a(n) = f^-1'(n) (note the 
derivative).


Now for an application:

Let S(n) = n^2. It's pretty easy that

    S(n) ~ f(n) = n^2

with function f on domain R. From our discussion above, there should be 
about

    f^-1(n) = sqrt(n)

elements of S <= n. The density of S near n is about

   d_S(n) = f^-1'(n) = 1/(2sqrt(n))


The Fibonacci sequence F is not strictly increasing (F(1) = F(2) = 1), but 
you failed to notice that. By other people's hard work, we know that

    F(n) ~ f(n) = c phi^n

where c = sqrt(5)/5 and phi = (sqrt(5)+1)/2. This means that there are about

    f^-1(n) = log(n)/log(phi) - log(c)/log(phi)

Fibonacci numbers <= n. This might be off by 1 or 2 because f is approximate 
and you failed to notice the repeated element earlier. But this is cowboy 
math, so let's ride on.

The density of Fibonacci numbers near n is about

    d_F(n) = f^-1'(n) = 1/(log(phi) n) ~= 2.078/n.

Note how taking the derivative nullifies the O(1) error you made earlier. 
This is the nature's way of telling us not to sweat the small stuff. A 
finite number of elements more or less do not affect the asymptotic density 
of an o(n) sequence.


For real function f, d_a(n) = f^1(n) can be thought of as an approximate 
probability that integer n occurs in a random integer sequence a ~ f.

For example, if f(n) = n^2 and a is a random integer sequence with a ~ f, 
the probability that 92 belongs to a can be guesstimated at around 1/(2 
sqrt(92)) = 10.4%.  This does not imply that 92 has 10.4% probability of 
belonging any specific a ~ f. For example, the probability that 92 is in 
sequence a(n) = n^2 + 2 is 0.

So let a and b be two random integer sequences with a ~ f and b ~ g.

By the above discussion, the probability that integer n is in a is about 
d_a(n), while the probability that n is in b is about d_b(n).

We conclude that the probability that n is in both a and b is d_a(n)*d_b(n).


So let's apply this discovery.

Should we expect that the number of square Fibonaccis SF is infinite or 
finite?

We foud above that the squares have density function d_S(n) = 1/(2 sqrt(n)) 
while the Fibonaccis have density function d_F(n) ~= 2.078/n.

This the square Fibonacci numbers should have density function d_SF(n) ~= 
d_S(n)*d_F(n) ~= 1.039 n^(-3/2) = h^-1'(n), where SF ~ h.

Integration gives h^-1(n) = -2.078 n^(-1/2) + C as the approximate number of 
elements of SF <= n.

We see that for large C, h^-1(n) approaches constant C, so we should expect 
a finite number of elements of SF. That is indeed the case: 0, 1 and 144 are 
the only square Fibonaccis.


Again, should we expect the number of square triangles ST to be infinite or 
finite?

We see that S ~ f : n->n^2 and T ~ g: g->n^2/2.

This gives d_S(n) = (1/2) n^(-1/2) and d_T(n) = (sqrt(2)/2) n^(-1/2).

The intersection ST should therefore have density about d_S(n)*d_T(n) = 
sqrt(2)/(4n) = h^-1'(n) where ST ~ h.

So the number of elements of ST <= n should be about h^-1(n) = (sqrt(2)/4) 
log(n) + C, which is unbounded.

We should expect an infinite number of square triangles, which is the case, 
vis A001110.


We shouldn't let a couple successes go to our heads, however.

In the last example, if we continue with our computations, we get h(n) = C 
exp(2 sqrt(2))^n =~ 4^n, whereas the actual square triangles grow as C 
(17+12 sqrt(2))^n =~ 34^n.

So while our statistical analysis correctly guessed the exponential behavior 
and infinitude of square triangles, it was wrong about the growth factor.

This is because the squares and triangles are not statistically independent. 
For example, half of triangular numbers are == 2 or 3 (mod 4), and cannot be 
square.

So the number of square triangles is sparser than a straightforward 
asymptotic density analysis would indicate.


In fact, we can always devise sequences that will fool this analysis.

For example, if S(n) = n^2 and T(n) = n^2+2 are disjoint, but our analysis 
predicts an infinite intersection based on asymptotic behavior alone.

Similarly, our analysis would predict an infinitude of square primes, based 
solely on their asymptotic behaviors.

Likewise, our analysis says that the set of powers of 2 that are also powers 
of 2 is finite (you read it right).

So this analysis should be used only to formulate tentative conjectures 
about the intersections of sequences that have no apparent correlation.


End of Lesson 1.


Homework:

Supposing the primes and the numbers of form x^2+1 are statistically 
independent, what should we conjecture about the finiteness and density of 
primes of the form x^2+1?