1970] RESEARCH7PROBLEMS 619
SOME PROBLEMS IN ADDITIVE NUMBER THEORY
P . ERDöS, Israel Institute of Technology, Haifa
1 . Let 1 < al < . . . < ak =< x be a sequence of integers for which the sums
k
(1) u Eiai, c-i = - 0 or 1
i=1
are all distinct . Put nlax k =.f(x) where the maximum is taken over all sequences
satisfying (1) . It is easy to see that
log x log log x
f(x) < 2 ± 0(1),
log 2 + lo bw
and Moser and I proved
log x log log x
(2) f(x) < 0(1) .
log 2 + 2 10 ~
b 2 +
'This is the best-known upper bound for f(x) .
Is it true that
(3) f(x) = (log x/log 2) + 0(1)?
1\Mloser and I asked : Is it true that f (2 11) >_ k+2 for sufficiently large k? Conway
and Guy showed that the answer is affirmative (unpublished) .
P . Erdös, Problems and results in additive number theory, Colloque, Théorie
des Nombres, Bruxelles 1955, p . 137 .
2 . Let 1 < a 1 < . . . < ak <_ x be a sequence of integers so that all the sums
ai,+ . . .+ais, i 1 <i 2 < . . . =< is, 1 < s <r
are distinct . Put max k=g r (x) . Turán and I proved
(4) 92(x) < X "' + O(X14)-
This was recently improved by Lindström to g2(x) <x112+x114+1 . The lower
bound g2(x) _>_ (1-+(1))x1/2 easily follows from a classical result of Singer on
difference sets . Turán and I conjectured
(5) g2(x) = X112 1 - 0(1) .
Bose and Chowla proved that gr(x) ? ( 1 dá--o(1))x 11 ' for each r >_ 2, and they con-
jectured
(6) gr(x) = ( 1 + o(1))x 11 ' .
This is known only for r = 2 .
R . C . Bose and S . Chowla, Theorems in the additive theory of numbers, Com-
ment . Math . Hel_v ., 37 (1962-63) 141-147 .
H . Halberstam and K . Roth, Sequences, Oxford Univ . Press, Oxford 1966 .
620 P . ERDŐS [June-July
P . Erdős and P . Turán, On the Problem of Sidon in additive number theory
and on some related problems, journal London Math . Soc ., 16 (1941) 212-215
J . Singer, A theorem in finite projective geometry and some applications to
number theory, Trans . Amer . Math . Soc ., 43 (1938) 377-385 .
B. Lindstrőm, An inequality for B2 sequences, Journal Combinatorial Theory,
6 (1969) 211-212 .
3. Let 1 _< di < • • • be an infinite sequence of integers . Denote by h(n) the
number of solutions of n=ai+a; . Turán and I conjectured that if h(n) >0 for
n > n o then
(7) lim sup h(n) _ .
n--
Another stronger conjecture states that if ak<ck 2 for every k then (7) holds.
These conjectures seem very difficult . It is a curious fact that the multiplica-
tive analogues of these conjectures are not intractable .
Let 1 < b l < • • • be an infinite sequence of integers . Denote by H(n) the
number of solutions of n = bib; . Assume H(n) > 0 for n > no . I proved
lim sup H(n) _ o c .
Turán and I further conjectured that the number of solutions of ai+a; =x
<
cannot be of the form cx+0(1), where c< cc . In other words
x
(8) Z h(n) = cx + 0(1)
n=1
can hold only if c = 0 and the sequence, a, < • • • , is finite . Fuchs and I proved
a very much stronger result than (8) . We in fact showed that if c > 0 then
x x lia
(9) 1:h(n) =cx+o
n=1 (log x) 12 )
is impossible . Jurkat showed (unpublished) that (9) is impossible even with
o(x 111) . Perhaps Jurkat's result is best possible and
x
E h(n)
n-1
= cx + 0(x1/,)
can hold for a suitable sequence a,<
Is it true that the number of solutions of a1+a ;+a, <_x cannot be of the form
cx+O(1) ? Our method used with Fuchs does not apply here .
I have several times offered $250 for the proof or disproof of any of the
conjectures (3), (5), or (7) .
Paul Erdős, On extremal problems of graphs and generalised graphs, Israel
Journal of Math ., 2 (1965) 183-190, and On the multiplicative representation of
1970] CLASSROOM NOTES 621
integers, ibid ., 2 (1965) 251-261 .
Paul Erdös and W . H . J . Fuchs, On a problem of additive number theory,
Journal London Math . Soc ., 31 (1956) 67-73 . See also the well-known book :
H . Halberstam and K. Roth, Sequences, Oxford Univ. Press, Oxford, 1966 .
A. Stohr, Gelöste and ungelöste Fragen über Basen der natürlichen Zahlen-
reihe, I and II, journal refine u . angew . Math ., 194 (1955) 40-65 and 111-140 .
CLASSROOM NOTES
EDITED BY DAVID DRASIN
Manuscripts for this Department should be sent to David Drasin, Division of Mathematical
Sciences, Purdue University, Lafayette, IN 47907 .
AN EXISTENCE THEOREM FOR NON-NOETHERIAN RINGS
ROBERT GILMER, Florida State University
In developing the theory of Noetherian rings, it is desirable to have at hand
some examples of non-Noetherian rings . One such example is the ring of poly-
nomials in infinitely many indeterminates over any nonzero ring . A second ex-
ample is R [X], where R is any nonzero commutative ring without identity [I],
but in this case, R [X] is also a ring without identity . We present here a theorem
which provides a method for constructing, as subrings of a polynomial ring in
finitely many indeterminates, a wide class of commutative rings with identity
which are not Noetherian . It should be noted that the proof of the theorem given
uses only one result (Lemma 1) outside the basic theory of Noetherian rings,
namely, that a finitely generated idempotent ideal of a commutative ring is
principal and is generated by an idempotent element . An examination of the proof
of this result reveals that even it is obtained as a direct application of Cramer's
Rule for determinants over a commutative ring with identity .
THEOREM 1 . Suppose that R is a nonzero commutative ring, that A is a nonzero
ideal of R distinct from R, and that { XX } XGA is a set of indeterminates over R . The
subring S = R+A [ { Xa } ] of R [ { Xa } ], consisting of those polynomials over R hav-
ing each of their nonconstant coefficients in A, is Noetherian if and only if these three
conditions hold : (1) A is finite, (2) R is Noetherian, and (3) the ideal A is idem-
potent.
Proof. Suppose that S is Noetherian . It is clear that A must life finite, for if
not, the ideal A [ { X x } ] of S would not be finitely generated . The mapping on S
which sends each polynomial f C S onto its constant term is a homomorphism
from S onto R, so that R is Noetherian . If v is a fixed element of A and if aCA,
the ideal (aX₉ aXQ, , aXó, ) of S is finitely generated, so that aXó {-I
E(aX , aXQ) for some positive integer m :
