Guy 1991 western number theory problems

../

problem_86_18: The 1991 restatement of the Erdős–Lacampagne–Selfridge problem 86:18: the deficiency of binom(n+k, k), the coefficients of deficiency 2 to 9 then known, the questions whether those of deficiency above 1 are finite in number and those of deficiency 1 infinite, and the remark's further examples; the source of Problem 1093.

problem_91_01: Erdős's 1991 question whether more than cn integers up to n, n large, always contain three with pairwise the same least common multiple, with its r-fold form, Pomerance's prime-factor variant and the union question for subsets of an n-set; the [Guy91] source of Problem 536.

problem_91_02: Erdős's 1991 question whether any n+2 integers in [1, 2n] include one equal to a sum of consecutive members, Pomerance's printed counterexample for n = 2k with k odd, k ≥ 5, and Erdős's follow-up conjecture that n + c members suffice; a finite form of the condition of Problem 839.

problem_91_03: The 1991 question of Erdős, Lacampagne and Selfridge for a good lower bound on g(k), whether g(k) > k^2 and even g(k) > k^3 for large k, with the remark reporting Erdős's g(k) > ck^2/ln k and Granville's hope of a bound beyond every power; the function of Problem 1095.

problem_91_05: Erdős's four 1991 Sidon questions: can a finite Sidon sequence be prolonged to a perfect difference set, or to one with a_n < (1+o(1))n^2; is there for each ε an infinite Sidon sequence with a_n < n^(2+ε); and does every n-term sequence contain a Sidon subsequence of (1+o(1))n^(1/2) terms; questions bearing on Problems 707, 44, 39 and 530.

problem_91_15: The 1991 question of Erdős and Graham whether every k-coloring of the integers has a monochromatic set of distinct integers whose reciprocals sum to 1, "open even for k = 2", with the threshold f(k) as its finite form; the coloring question of Problem 46.

problem_91_16: Erdős's 1991 question whether, over representations 1 = 1/x_1 + ... + 1/x_n with x_1 < ... < x_n, the lim inf of x_n/x_1 exceeds e, with his remark that it is trivially at least e and perhaps infinite; a ratio question beside the 1980 one recorded on Problem 284.

problem_91_17: Erdős's 1991 question whether every representation 1 = 1/x_1 + ... + 1/x_n has a gap x_{i+1} − x_i of at least 3, with {2,3,6} showing that more than 3 cannot be asked and the guess that bounded gaps allow only finitely many solutions; the question of Problem 287.

problem_91_18: The 1991 question of Erdős and Joó: for 1 < q < 1 + ε, order the finite sums of distinct powers q^i and prove that consecutive gaps tend to 0 when ε is small, perhaps for every q below the smallest Pisot number; the [GWNT91] source of Problem 1096.

---

Western Number Theory Problems, 1991-12-19 & 22, edited by Richard K. Guy, "for mailing prior to 1992 (Corvallis) meeting", dated 92-08-20 and issued from the Department of Mathematics and Statistics, The University of Calgary (p. 1). The problems proposed at the 1991 Asilomar meeting are numbered 91:01--91:25 (p. 1's summary of earlier meetings gives the old and new numbering of the sets since 1967), with comments on the earlier problems 76:15, 76:44, 86:18, 87:02, 88:09, 88:12, 89:20, 90:07, 90:10, 90:17, 90:18 and 90:20. The site's reference key [Guy91] for Problem 536 names this set; the site links the PDF below.

The copy read for this card is the conference site's copier scan of the typeset set: eighteen pages with no text layer, printed page $n$ = PDF p. $n$. Provenance: retrieved from https://westcoastnumbertheory.org/wp-content/uploads/2018/02/wcnt-problems-1991.pdf (HTTP 200, one request; the link on the site's Problem 536 page); 13,746,604 bytes. No notice is printed in the file (PDF pp. 1 and 18 read on the page images); the hosting conference site (https://westcoastnumbertheory.org/, read 2026-10-02) states no copyright, license or terms of use; the term is unstated.

Read status: claims checked for problems 91:01--91:05 (pp. 9--10), 91:15--91:18 (pp. 15--16) and the comment on 86:18 (pp. 3--4), read clause by clause on the page images; the other pages were read on the page images for the layout below only. The set records problems, remarks and reported results, not proofs. Pomerance's counterexample under 91:02 was checked here by computation for odd $k$ from $5$ to $15$, and the deficiencies printed under 86:18 were recomputed from the definition; the result pages record both checks. Nothing here is independently reviewed.

Contents

Layout: p. 1 title and summary; p. 2 a request for copies of correspondence with D. H. Lehmer for the Bancroft Library, with John Brillhart's list of Lehmer's students; p. 3 preprints and the start of the comments on earlier problems (76:15, 76:44, 86:18); pp. 4--8 the remaining comments (86:18 continued, 87:02, 88:09, 88:12, 89:20, 90:07, 90:10, 90:17, 90:18, 90:20); pp. 9--18 "Problems proposed 91-12-19 & 22", 91:01--91:04 (p. 9), 91:05 (p. 10), 91:06 (pp. 10--11), 91:07 (p. 11), 91:08 (pp. 11--12, with Pomerance's solution on p. 12), 91:09--91:10 (p. 13), 91:11 (pp. 13--14), 91:12--91:13 (p. 14), 91:14--91:17 (p. 15), 91:18 (p. 16), 91:19 (pp. 16--17), 91:20--91:21 (p. 17), 91:22 (pp. 17--18), 91:23--91:25 (p. 18).

The Erdős items, each question quoted as posed and the editor's remarks restated:

• 91:01 (Paul Erdős), p. 9: "Let $1\le a_1<a_2<\ldots<a_k\le n$, $k>cn$. Is it true that if $n>n_0(c)$, there are always three $a_i$ which have pairwise the same least common multiple? More generally, are there $r$ of the $a_i$ which have pairwise the same least common multiple? Pomerance asks: can one prove that there are three $a_i$ so that the least common multiple of every two has the same prime factors? Perhaps a related combinatorial problem asks: Let $|S|=n$, $A_i\subset S$ for $1\le i\le t_n$. What is the smallest $t_n$ which ensures that there are three $A_i$ which have pairwise the same union?"
• 91:02 (Paul Erdős), p. 9: "Is it true that if $1\le a_1<a_2<\ldots<a_{n+2}\le2n$, then some $a_j$ is a sum of consecutive $a_i$?" Since Pomerance's solution below answers no, the item adds Erdős's question for the least number that can replace $n+2$, with his conjecture that it is $n+c$ for some constant $c$. Solution (Carl Pomerance): false for $n=2k$ with $k$ odd, $k\ge5$, by the set $\{k-1,k,k+1,\tfrac{3k-1}2,\tfrac{3k+1}2\}\cup\{2k,\ldots,4k\}\setminus\{2k+1,\tfrac{5k+1}2,3k,\tfrac{7k+1}2\}$; example $k=5$: $\{4,5,6,7,8,10,12,14,16,17,19,20\}$. No catalog problem states this finite form; Problem 839 asks the infinite version.
• 91:03 (Paul Erdős, Carole Lacampagne & John Selfridge), p. 9: "Obtain a good lower bound for $g(k)$, the least integer $>k+1$ such that $\gcd\left(\binom{g(k)}k,k!\right)=1$. Is it true that for $k>k_0$, $g(k)>k^2$? In fact, is it true that for $k_1>k_0$, $g(k_1)>k_1^3$?" The editor's remark points to 86:18 above, notes that a deficient binomial coefficient $\binom{n+k}k$ must have $n+k\ge g(k)$, and reports that Lacampagne later wrote that Erdős had proved $g(k)>ck^2/\ln k$ for large $k$ and that Granville thought he might be able to prove $g(k)$ larger than any power of $k$ for large $k$.
• 91:04 (Paul Erdős), p. 9: "Let $a_1<a_2<\ldots<a_k\le n$ be a Sidon sequence, i.e., all the sums $a_i+a_j$ are distinct. Is it true that $\frac1{\ln x}\sum_{a_i+a_j\le x}\frac1{a_i+a_j}\to0$ as $x\to\infty$? In fact perhaps $\sum_{a_i+a_j<x}\frac1{a_i+a_j}<c_1\ln\ln x$. It is known that it can be $>c_2\ln\ln x$." No catalog problem was located for this item.
• 91:05 (Paul Erdős), p. 10, four questions on a Sidon sequence $a_1<a_2<\ldots<a_k$: "Can it be prolonged to a perfect difference set, i.e., $a_1<a_2<\ldots<a_k<a_{k+1}<\ldots<a_{p+1}=p^2+p+1$ so that the differences $a_u-a_v$, $1\le u,v\le p+1$, $u\ne v$, represent every nonzero residue mod $p^2+p+1$ exactly once? I could not even decide if it can be prolonged to $a_1<a_2<\ldots<a_k<a_{k+1}<\ldots<a_n$, $a_n<(1+o(1))n^2$, i.e., if it can be made as dense as possible asymptotically." Is there for every $\epsilon>0$ an infinite Sidon sequence with $a_n<n^{2+\epsilon}$ for $n>n_0(\epsilon)$? Rényi and Erdős proved (Halberstam and Roth, Sequences, p. 111, Theorem 2) that some sequence with $a_n<n^{2+\epsilon}$ has at most $k$ solutions of $a_i+a_j=t$ for every $t$; Ajtai, Komlós and Szemerédi proved that a Sidon sequence with $a_n<cn^3/\ln n$ exists. Does every sequence $a_1<a_2<\ldots<a_n$ contain a Sidon subsequence with $m=(1+o(1))n^{1/2}$ terms? Komlós, Sulyok and Szemerédi proved this with $m>cn^{1/2}$ (the page prints "Sulyork").
• 91:15 (Paul Erdős & Ron Graham), p. 15: "Is it true that any coloring of the integers with $k$ colors gives a monochromatic solution of $\sum\frac1{x_i}=1$, $x_1<x_2<\ldots$ (finite sum)? This is open even for $k=2$. If the answer is affirmative, let $f(k)$ be the smallest integer for which every $k$-coloring of the integers $1\le t\le f(k)$ contains a monochromatic solution. Determine or estimate $f(k)$."
• 91:16 (Paul Erdős), p. 15: "Is it true that if $\frac1{x_1}+\frac1{x_2}+\ldots+\frac1{x_n}=1$, $x_1<x_2<\ldots<x_n$ then $\liminf\frac{x_n}{x_1}>e$? It is trivial that the limit is $\ge e$. In fact perhaps it is infinite."
• 91:17 (Paul Erdős), p. 15: "Is it true that for every solution of $\frac1{x_1}+\frac1{x_2}+\ldots+\frac1{x_n}=1$, $\max(x_{i+1}-x_i)\ge3$? $\{2,3,6\}$ shows that $>3$ is not true but perhaps this is the only counterexample. Perhaps $\max(x_{i+1}-x_i)\le k$ has only a finite number of solutions."
• 91:18 (Paul Erdős & I. Joó; the page prints "Jóó"), p. 16: "Let $1<q<1+\epsilon$. Consider all the numbers $\sum_{i=0}^n\epsilon_iq^i$, $\epsilon_i=0$ or $1$, $1\le n<\infty$ ordered by size, $1<x_1<x_2<\ldots$. Prove that if $\epsilon$ is sufficiently small then $x_{k+1}-x_k\to0$. Perhaps if $q<q_0$, $q_0^3=q_0+1$ (the smallest Pisot-Vijayaraghavan number) then $x_{k+1}-x_k\to0$."
• Comment on 86:18 (P. Erdős, C. B. Lacampagne & J. L. Selfridge), pp. 3--4: the deficiency of $\binom{n+k}k$, $k\le n$, is the number of $i$ with $b_i=1$ where $n+i=a_ib_i$, $1\le i\le k$, the prime factors of $b_i$ exceed $k$ and $\prod a_i=k!$; $\binom{44}8,\binom{74}{10},\binom{174}{12},\binom{239}{14}$ have deficiency 2, $\binom{46}{10},\binom{47}{10},\binom{241}{16}$ deficiency 3, $\binom{47}{11}$ deficiency 4 and $\binom{284}{28}$ deficiency 9; "Are there others with deficiency greater than 1? Only finitely many? Are there infinitely many with deficiency 1?" Remark (p. 4): $\binom{5179}{27},\binom{8113}{28},\binom{8114}{28},\binom{96022}{42}$ have deficiency 2 and $\binom{2105}{25},\binom{1119}{27},\binom{6459}{33}$ deficiency 3; "These are the only binomial coefficients with $k+n<k^3$ and $k\le101$ which have deficiencies." The range as printed does not contain the remark's own $\binom{96022}{42}$, whose $k+n=96022$ exceeds $42^3=74088$. As printed, $\binom{8113}{28}$, $\binom{8114}{28}$ and $\binom{96022}{42}$ are divisible by primes at most $k$, so their deficiency is not defined; the result page records the recomputation and the values $\binom{8413}{28}$, $\binom{8414}{28}$, $\binom{96622}{42}$ that have deficiency $2$. The remark points to 91:03.

Compiled scope

A problem collection: the Erdős items are recorded from the page images as questions and reported results; the only proof in them is Pomerance's construction under 91:02. Items not by Erdős were read for the layout only.

Results. Problem 86:18 and its remark, pp. 3--4 (the deficiency of a binomial coefficient); Problem 91:01, p. 9 (three integers with pairwise the same least common multiple, and the union question); Problem 91:02, p. 9 (sums of consecutive members, with Pomerance's counterexample); Problem 91:03, p. 9 (lower bounds for $g(k)$); Problem 91:05, p. 10 (the four Sidon questions); Problem 91:15, p. 15 (monochromatic representations of $1$ by unit fractions); Problem 91:16, p. 15 (the ratio $x_n/x_1$); Problem 91:17, p. 15 (gaps between denominators); Problem 91:18, p. 16 (gaps between sums of powers of $q$). Problem 91:04 (p. 9), Erdős's question on reciprocal sums over a Sidon sequence, has no page: no catalog problem or corpus page was found that it bears on.

Bears on. Each row says what the item poses; none of the items records a result that settles a problem.

• #536: the first question of 91:01 (p. 9) is the problem's density question, whether $f(N)=o(N)$, and is the site's [Guy91]; the $r$-fold generalization and Pomerance's prime-factor variant asked beside it are not part of the problem.
• #857: the third paragraph of 91:01 asks for the least $t_n$ forcing three subsets of an $n$-set with pairwise the same union; taking complements, this is the problem's $m(n,3)$ (three sets with pairwise the same intersection), posed as "perhaps a related combinatorial problem" beside the lcm question.
• #839: 91:02 (p. 9) asks about the problem's avoidance condition (no member a sum of consecutive members) for finite sets in $[1,2n]$ rather than infinite sequences; Pomerance's printed sets have the condition and $n+2$ members in $[1,2n]$ for $n=2k$, $k$ odd, $k\ge5$. The set draws no consequence for the problem.
• #1095: 91:03 (p. 9) defines the problem's $g(k)$ and asks for a lower bound, whether $g(k)>k^2$ and whether $g(k_1)>k_1^3$; its remark reports Erdős's $g(k)>ck^2/\ln k$ and Granville's hope of a bound beyond every power of $k$, both without proof.
• #1093: the comment on 86:18 (pp. 3--4) defines the problem's deficiency, lists coefficients of deficiency greater than $1$ and asks the problem's two questions; its remark claims completeness of the list for $k+n<k^3$, $k\le101$, and the 91:03 remark gives $n+k\ge g(k)$ for every coefficient with a deficiency. This is finite evidence and settles neither question.
• #707: the first question of 91:05 (p. 10) asks whether a finite Sidon sequence can be prolonged, by terms above its largest, to a perfect difference set modulo $p^2+p+1$ whose largest member is $p^2+p+1$. The problem asks only for a superset that is a perfect difference set modulo $p^2+p+1$ for a prime $p$, and the print does not say that $p$ is prime. An affirmative answer to the item with $p$ prime would answer the problem; the questions are not the same.
• #44: the second question of 91:05 asks for an infinite Sidon prolongation with $a_n<(1+o(1))n^2$; when $N$ is the largest member of $A$, an affirmative answer gives the problem's extension to a Sidon set of size $(1-\epsilon)M^{1/2}$ in $\{1,\ldots,M\}$. Erdős "could not even decide" it.
• #39: the third question of 91:05, for each $\epsilon>0$ an infinite Sidon sequence with $a_n<n^{2+\epsilon}$ for $n>n_0(\epsilon)$, lets the sequence depend on $\epsilon$ as worded, so it is weaker than the problem's one set $A$ with $|A\cap\{1,\ldots,N\}|\gg_\epsilon N^{1/2-\epsilon}$ for every $\epsilon$; the item reports the Erdős--Rényi bounded-multiplicity sequence and the Ajtai--Komlós--Szemerédi $cn^3/\ln n$ bound.
• #530: the fourth question of 91:05, a Sidon subsequence of $(1+o(1))n^{1/2}$ terms in every $n$-term sequence of integers, is the problem's $\ell(N)\sim N^{1/2}$ for integers (the problem takes reals), with the Komlós--Sulyok--Szemerédi bound $m>cn^{1/2}$ reported.
• #46: 91:15 (p. 15), attributed to Erdős and Graham, is the problem's coloring question when read, as the problem states it, with denominators at least $2$ (the print does not exclude the one-term solution $1/1$); it was "open even for $k=2$" in 1991, and the threshold $f(k)$ is a finite form the problem does not ask for.
• #284: 91:16 (p. 15) asks whether $\liminf x_n/x_1>e$ over representations $\sum1/x_i=1$ and suggests it may be infinite. It is not the problem's question; it is the opposite expectation to the 1980 ratio question ($\min x_n/x_1\to e$) that the problem's page records beside it.
• #287: 91:17 (p. 15) asks the problem's question, $\max(x_{i+1}-x_i)\ge3$ for every representation of $1$, with $\{2,3,6\}$ showing that $>3$ fails, the guess that it is the only representation with maximal gap at most $3$, and the finiteness guess for bounded gaps.
• #1096: 91:18 (p. 16), attributed to Erdős and Joó, asks the problem's question $x_{k+1}-x_k\to0$ for $q$ close to $1$, with the guess that this holds for every $q$ below the smallest Pisot number $q_0$ ($q_0^3=q_0+1$).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.