[seqfan] Re: An arithmetic conjecture
David Wilson
davidwwilson at comcast.net
Sat Mar 7 20:48:39 CET 2009
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?
More information about the SeqFan
mailing list