Problem 1180

Let $\epsilon>0$ . Does there exist a constant $C_\epsilon$ such that, for all primes $p$ , every residue modulo $p$ is the sum of at most $C_\epsilon$ many elements of

\{ n^{-1} : 1\leq n\leq p^\epsilon\}

where $n^{-1}$ denotes the inverse of $n$ modulo $p$ ?

Source: erdosproblems.com/1180

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, in the site's label. Shparlinski's Theorem 3 (Arch. Math. 78 (2002), 445--448, refereed), an accepted full claim on its page, gave the first affirmative answer: for every $\epsilon>0$ , every sufficiently large prime $p$ and every integer $c$ , $k=4\epsilon^{-3}+O(\epsilon^{-2})$ pairwise distinct $x_i\le p^\epsilon$ with $\sum x_i^{-1}\equiv c\pmod p$ , the site's $C_\epsilon\ll\epsilon^{-3}$ for $p\ge p_0(\epsilon)$ , which the authored small-prime remark below extends to every prime with repetition allowed. Also first-hand: Croot's Theorem 2 with $k=1$ (Integers 4 (2004), Paper A20, refereed; the journal's text agrees with arXiv v2), on its page, for every $0<\epsilon\le1$ an $N(\epsilon,1)$ such that every residue modulo every prime $p\ge2$ is a sum of $N$ inverses of integers in $[1,p^\epsilon]$ , read with at most $N$ summands, as the question asks and the proof's small-prime step gives (as printed, with exactly $N$ , the primes with $p^\epsilon<2$ fail), which extends to all $\epsilon$ by the monotonicity remark; and Glibichuk's Theorem 3 (Mat. Zametki 79 (2006), 384--395, refereed; in Russian), on its page, $N=8([1/\epsilon+1/2]+1)^2$ pairwise distinct summands for all sufficiently large $p$ , the site's $C_\epsilon\ll\epsilon^{-2}$ , which an authored one-line remark below extends to the remaining finitely many primes with repetition allowed. The three pages are accepted full claims, and the frontmatter standing is derived from them. The trivial lower bound $C_\epsilon\gg\epsilon^{-1}$ (the site's remark) follows from counting; the true order of $C_\epsilon$ between $\epsilon^{-1}$ and $\epsilon^{-2}$ is open.

Gl06: Glibichuk, A. A., Combinatorial properties of sets of residues modulo a prime and the Erdős--Graham problem. Mat. Zametki 79 (2006), no. 3, 384--395, DOI 10.4213/mzm2708 (in Russian; received 3 May 2005, revised 26 September 2005); English translation Math. Notes 79 (2006), no. 3--4, 356--365, DOI 10.1007/s11006-006-0040-8 (not held). Theorem 3, p. 385; the introduction, p. 384. Library home: Glibichuk 2006; result page Glibichuk 2006, Theorem 3.
Cr04: Croot, E., Sums of the form $1/x_1^k+\cdots+1/x_n^k$ modulo a prime. Integers 4 (2004), Paper A20 (the journal's volume contents and the Zenodo deposit, DOI 10.5281/zenodo.7642509, accessed 2026-09-18); arXiv:math/0403360 (v1 22 March 2004, v2 21 October 2004). The journal's text agrees with arXiv v2; v1 and the copy on the author's papers page keep v1's introduction, Theorem 2 and five-entry reference list. Theorem 2, p. 2. Library home: Croot 2004; result page Croot 2004, Theorem 2.
Cr99: Croot, III, E. S., On some questions of Erdős and Graham about Egyptian fractions. Mathematika 46 (1999), no. 2, 359--372, DOI 10.1112/S0025579300007828. Proposition 2 (pp. 4--5 of the author's typescript): the source of the site's $(\log p)^{3+o(1)}$ bound, as Glibichuk's introduction attributes it. Library home: Crootiii 1999.
Sh02: Shparlinski, Igor E., On a question of Erdős and Graham. Arch. Math. (Basel) 78 (2002), no. 6, 445--448, DOI 10.1007/s00013-002-8269-2 (received 30 August 2000). Theorem 3, p. 446; the introduction, p. 445. Library home: Shparlinski 2002; result page Shparlinski 2002, Theorem 3.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980). Printed p. 103: the passage below. Library home: Erdős and Graham 1980. - Not held and not requested: Karatsuba's papers cited by [Sh02] (its [4]--[5]) and [Gl06] (its [4]--[6]), the Friedlander--Iwaniec Brun--Titchmarsh paper cited by [Sh02] (its [3]) and the Bourgain--Katz--Tao preprint cited by [Cr04] (its [1]).

Problem 1180

Status

Proof claims

Discussion