Some probabilistic remarks on Fermat's Last Theorem

By P. Erdös and S. Ulam

Annotated on Fermat's Library with 0 comments. Text and annotations as Markdown Original paper

ROCKY MOUNTAIN
JOURNAL OF MATHEMATICS
Volume 1, Number 4, Fall 1971
SOME PROBABILISTIC REMARKS ON FERMAT'S
LAST THEOREM
P. ERDÖS AND S. ULAM
Let a i < a
2
< '
* *
be an infinite sequence of integers satisfying
ö
n
= (c H- o(l))n
a
for some a > 1. One can ask: Is it likely that
d{ + dj = a
r
or, more generally, a
ix
+ • • • + a
in
= a
if
has infinitely
many solutions. We will formulate this problem precisely and show
that if a > 3 then with probability 1, ü{ +
Oj
= a
r
has only finitely
many solutions, but for a ^ 3, a* + a, = a
r
has with probability 1
infinitely many solutions. Several related questions will also be
discussed.
Following [1] we define a measure in the space of sequences of
integers. Let a > 1 be any real number. The measure of the set of
sequences containing n has measure Cin
l,oc
~
l
and the measure of the
set of sequences not containing n has measure 1
—
Cin
1/a_1
. It easily
follows from the law of large numbers (see [1]) that for almost all
sequences A = {a
x
< a
2
< '
*
•} ("almost all" of course, means that
we neglect a set of sequences which has measure 0 in our measure)
we have
(1) A(x) = (1 + o(l))
Cl
i -i- = (i +
0
(i))
Ciaac
iA.
n = l
n
where A(x) = ^
a <x
1. (1) implies that for almost all sequences A
(2) a
n
= (1 + o(l))(n/ca)«
Now we prove the following
THEOREM. Let a > 3. Then for almost all A
(3) ai 4-
Oj
= a
r
has only a finite number of solutions. Ifa=3, then for almost all A,
(3) has infinitely many solutions.
It is well known that r
3
+ y
3
= z
3
has no solutions, thus the se-
quence {n
3
} belongs to the exceptional set of measure 0.
Assume a > 3. Denote by E
a
the expected number of solutions of
ai -I- aj = a
r
. We show that E
a
is finite and this will immediately
Received by the editors April 28, 1970.
AMS 1970 subject
classifications.
Primary 10K99, 10L10.
Copyright
©
Rocky Mountain Mathematics Consortium
613
614
P.
ERDOS AND S. ULAM
imply that for almost all sequences A, a* +
Oj
= a
r
has only a finite
number of solutions. Denote by P(u) the probability (or measure)
that u is in A. We evidently have
00
E
a
=
S P(n) S P(u)P(v)
n
= l u+v=n
=
Cl
3 y _-L_ y 1
1
^
n
l-l/a ^
u
l-lla
v
l-lla
n =
l
n
u+v=n
u v
<
c
2 S
TINTÂT
^T^r
= c
2 S 7i~s; <
c
3
n = 1
n n
n=1
rc
which proves our theorem for a > 3. One could calculate the prob-
ability that (3) has exactly r solutions (r = 0, 1, • • •).
Let now a = 3. The case a = 3 is the most interesting; the case
a < 3 can be dealt with similarly. Denote by E
a
(x) the expected
number of solutions of
(3)
if
cu,
ÜJ
and a
r
are ^ x. We have
E,(x)
= ± P(n) S
P(u)P(v)
=
Cl
3 £ -L S-J-
n=l
u+ü=n n=l '* u+ü=n \
ul
V
(4)
=
(1 +
0
(l))
Cl
3 Ì^-|=(l+
0(l))
Cl
3
C2
log*.
n = l
n n
By a little calculation, it would be easy to determine c
2
explicitly.
Now we prove by a simple second moment argument that for almost
all A the number of solutions /
3
(
A,
x) of a
{
+ üj = a
r
, a
r
^x satisfies
(5) /
3
(A, x) = (1 + o(l)Wc
2
log x, that is /
3
(A, x)/E
3
(x) -> 1.
To prove (5) we first compute the expected value off
3
(A, x)
2
.
The expected value of/
3
(A, x) was E
3
(x) which we computed in
(4).
Denote by E
3
2
(x) the expected value of/
3
(A, x)
2
. We evidently
have
(6) E
3
2
(*) = S P(ni)P(n
2
) £ P(u
u
u
2
,
Vl
, v
2
)
where F(wx, t>
1?
W
2
,
t;
2
) is the probability that u
Ì7
V\, u
2
, v
2
occurs in
our sequence. If these four numbers are distinct, then clearly
P(u
h
u
2
, v
u
v
2
) = P(ui)P(u
2
)P(vi)P(v
2
), but if say u
Y
= u
2
, the prob-
ability is larger. Hence E
3
2
(x) > (E
3
(x))
2
and to get the opposite
inequality we have to add a term which takes into account that the
four terms do not have to be distinct, or r^ < n
2
,
Wi
= u
2
.
PROBABILISTIC REMARKS ON FERMATES LAST THEOREM 615
E
3
?(x) < (E
3
(*))
2
+ cÌ
PMPin,
+ v
2
- Vi) S
P^Ffo)!^)
nj
= 1
Uj
4-Uj
=nj ; v
2
<
x
< (EM)
2
+ Ì.-T- 2 WK + o
2
-
0l
)
(7) », =i
n
i«
2
=i
< (£
3
(*))
2
+ i - i PM
2
<
(E
3
(x))
2
+
t f
nj = l
n
l u
2
=l n = l
n
<(E
3
(x)
2
) + c
3
logx.
Thus
(8) (E
3
(x
2
)) < E
3
2
(x) < (E
3
(x))
2
+ c
3
log x.
(8) implies by the Tchebycheff inequality that the measure of the set
A for which
(9) \f
3
(A,x)-E
3
(x)\>elogx
is less than ck
2
log x. This easily implies that for almost all A
(10) lim/
3
(A,x)/E
3
(x)=l.
To show (10) let x
k
=
2
k
<
l
<>&
*>
2
.
From (9) and the Borei-Cantelli
Lemma it follows that
(11) lim/
3
(4x)/£
3
(x
fc
)=l.
k= »
(11) now easily implies (10), ^(A, x) is a nondecreasing function of
x, thus if x
k
< x <
x
k+l
,
/
3
(A, x
k
) ê /
3
(A
?
ac)S/
3
(A, **+i). Thus (11)
follows from E
3
(x
n
)IE
3
(x
k
+i)
—»
1.
By the same method we can prove that for a < 3
*=«> E
a
(x)
Similarly we can investigate the equation
(12) a
Cr
= a
Cl
+
a
C2
+
• • •
+a
Cx
.
Here by the same method we can prove that for a > fc + 1 with
probability 1, (12) has only a finite number of solutions and for
aSH 1 it has infinitely many solutions.
Euler conjectured that the sum of fc — 1 (fcth) powers is never a
fcth power. This is true for fc = 3, unknown for fc = 4 and has been
recently disproved for fc = 5 [2]. As far as we know it is possible that
616
P.
ERDOS AND S. ULAM
for every
t§3
there
are
only
a
finite number
of
fcth powers which
are
the sum of
k — 1
or
fewer fcth powers.
Let/3
> 1 be a
rational number.
One can ask
whether
[n
ß
] + [m
ß
]
=
[l
ß
], has
solutions
in
integers
n, m, I. One
would guess that
for
ß
< 3 the
equation always
has
infinitely many solutions
but
that
the
measure
of the set in ß, ß > 3, for
which
it has
infinitely many solu-
tions
has
measure
0, but it is not
hard
to
prove that
the ß's for
which
it has
infinitely many solutions
is
everywhere dense.
REFERENCES
1.
P.
Erdös
and A.
Rényi, Additive properties
of
random sequences
of
positive integers, Acta Arith.
6
(1960), 83-110.
MR 22
#10970;
See
also:
H. Halberstam
and K. F.
Roth, Sequences,
Vol. 1,
Clarendon Press, Oxford,
1966.
MR 35
#1565.
2.
L. J.
Lander
and T.
Parkin,
A
counterexample
to
Euler's
sum of
powers
conjecture, Math. Comp.
21
(1967), 101-103.
MR 36
#3721.
UNIVERSITY
OF
COLORADO, BOULDER, COLORADO
80302

Discussion

Tap the paper where you want to comment