Erdős Problem #445

Erdős Problem 445 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/445

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/445.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/445.tex.

Is it true that, for any $c>1/2$, if $p$ is a sufficiently large prime then, for any $n\geq 0$, there exist $a,b\in(n,n+p^c)$ such that $ab\equiv 1\pmod{p}$? Heilbronn (unpublished) proved this for $c$ sufficiently close to $1$. Heath-Brown [He00] used Kloosterman sums to prove this for all $c>3/4$. This is discussed in this MathOverflow question . References [He00] Heath-Brown, D. R., Arithmetic applications of {K}loosterman sums . Nieuw Arch. Wiskd. $5$ $2000$, 380--384.

FORMAL RESTATEMENT

Fix a real $c>\tfrac12$. For a prime $p$ and integer $n\ge 0$, define the integer interval \[ I_{n,p,c}:=\{a\in\mathbb Z: n<a<n+p^c\}. \] Question: is it true that for every $c>\tfrac12$ there exists $p_0(c)$ such that for every prime $p\ge p_0(c)$ and every integer $n\ge 0$ there exist $a,b\in I_{n,p,c}$ with \[ ab\equiv 1\pmod p? \] Equivalently: does every length-$\asymp p^c$ interval contain an element whose multiplicative inverse modulo $p$ also lies in the same interval?

Stress points: - the threshold $c=1/2$ is natural because inversion is a permutation on $(\mathbb Z/p\mathbb Z)^*$ and "random" intersection heuristics suggest $p^c$ needs to exceed $\sqrt p$.

QUICK LITERATURE/CONTEXT CHECK

I do not use any results beyond those explicitly stated here: Heilbronn proved the statement for $c$ close to $1$, and Heath-Brown proved it for all $c>3/4$ using Kloosterman sums.

ATTACK PLAN

Proof track (elementary bounds): 1) Prove a necessary condition: if an interval length $L$ works uniformly for all shifts $n$, then necessarily $L\gtrsim \sqrt p$ by a counting argument. 2) Prove a trivial sufficient condition for very long intervals (e.g. length $>\tfrac{p-1}{2}$) using a pigeonhole argument in the multiplicative group.

Disproof track: Try to produce explicit primes $p$ and shifts $n$ where an interval of length $\lfloor p^c\rfloor$ avoids its inverse set; a counting argument suggests this should be possible when $c<1/2$.

I carry out $1$ and $2$ rigorously and perform a small computation of the minimal interval length that works for all shifts for primes $p\le 200$.

WORK

FAST REALITY CHECK (small primes). For each prime $p\le 200$, I computed the minimal integer $L=L(p)$ such that for every residue class shift $n\pmod p$, the set of residues represented by $\{n+1,\dots,n+L\}$ (excluding $0$) contains some $a$ with $a^{-1}$ also in the same set. The ratios $L/\sqrt p$ varied between about $0.89$ and $2.97$ in this range; the worst case up to $200$ was $p=131$ with $L=34$. Selected values:

5 2 0.8944271909999159
7 3 1.1338934190276817
11 5 1.507556722888818
13 6 1.6641005886756874
17 7 1.697749375254331
23 9 1.876629726513673
37 13 2.137186834969645
...
max ratio L/sqrt(p) up to 200: 2.970593792647529 at (131, 34, 2.970593792647529)

This supports (but does not prove) the heuristic that the critical scale is $\asymp \sqrt p$.

Lemma 445.1 (elementary $\sqrt p$ barrier for uniform-in-$n$ statements). Let $p$ be an odd prime and let $L$ be an integer with $1\le L\le p-1$. Suppose that for every residue class $n\in\mathbb Z/p\mathbb Z$ there exist integers $1\le i\le j\le L$ such that \[ (n+i)(n+j)\equiv 1\pmod p. \] Then necessarily \[ L(L+1)\ge p. \] In particular, if $L(L+1)<p$ then there exists $n\pmod p$ such that no such pair exists.

Proof. For each $n\in\mathbb Z/p\mathbb Z$, define \[ Y_n := \#\left\{(i,j): 1\le i\le j\le L\text{ and }(n+i)(n+j)\equiv 1\pmod p\right\}. \] By hypothesis, $Y_n\ge 1$ for every $n$, hence \begin{equation} \sum_{n\in\mathbb Z/p\mathbb Z} Y_n \ge p. \tag{1} \end{equation}

On the other hand, fix a pair $(i,j)$ with $1\le i\le j\le L$. The congruence \[(n+i)(n+j)\equiv 1\pmod p\] expands to a quadratic congruence in $n$: \[n^2 + (i+j)n + (ij-1)\equiv 0\pmod p. \] Over the field $\mathbb F_p$, a nonzero polynomial of degree $2$ has at most $2$ roots. (Here the polynomial is not identically zero because its leading coefficient is $1\not\equiv 0\pmod p$.) Therefore, for each fixed $(i,j)$ there are at most $2$ values of $n\in\mathbb Z/p\mathbb Z$ that satisfy the congruence.

Summing over all pairs $(i,j)$ gives \[ \sum_{n\in\mathbb Z/p\mathbb Z} Y_n \le 2\cdot \#\{(i,j): 1\le i\le j\le L\} =2\cdot \frac{L(L+1)}{2}=L(L+1). \tag{2} \] Combining $1$ and $2$ yields $p\le L(L+1)$, as claimed. $\Box$

Lemma 445.2 (very long intervals always work). Let $p$ be an odd prime and let $S\subseteq\mathbb F_p^*$ be any subset with $|S|>\tfrac{p-1}{2}$. Then $S\cap S^{-1}\ne\varnothing$, where $S^{-1}:=\{x^{-1}:x\in S\}$. Consequently, if an interval $I\subseteq\{1,2,\dots,p-1\}$ has length $>\tfrac{p-1}{2}$, then there exist $a,b\in I$ with $ab\equiv 1\pmod p$.

Proof. The inversion map $x\mapsto x^{-1}$ is a bijection of $\mathbb F_p^*$, hence $|S^{-1}|=|S|$. If $S\cap S^{-1}=\varnothing$, then \[|S\cup S^{-1}| = |S|+|S^{-1}| = 2|S| > p-1, \] which is impossible since $S\cup S^{-1}\subseteq\mathbb F_p^*$ has size at most $p-1$. Therefore $S\cap S^{-1}\ne\varnothing$.

For the interval consequence, take $S$ to be the set of residue classes represented by the interval (excluding $0$), and apply the first part: an element $a\in S\cap S^{-1}$ means $a\in S$ and $a^{-1}\in S$, i.e. two elements of the interval multiply to $1\pmod p$. $\Box$

VERIFICATION

- Lemma 445.1: The only nontrivial facts are (a) quadratic polynomials over a field have at most two roots, and (b) the polynomial is genuinely degree 2 because the coefficient of $n^2$ is $1$. Both are correct. - Lemma 445.2: uses only that inversion is a bijection. - Matching the original quantifiers: Lemma 445.1 addresses the uniform-in-$n$ requirement (for every shift). It provides a necessary condition $L\gtrsim\sqrt p$, aligning with the stated threshold $c>1/2$.

FINAL

UNRESOLVED

(i) Strongest proved partial result: For any prime $p$, if an interval length $L$ works for every shift $n$ (i.e. always contains $a,b$ with $ab\equiv1\pmod p$), then $L(L+1)\ge p$ (Lemma 445.1), giving an elementary $\sqrt p$ barrier. Also, intervals representing more than half of $(\mathbb Z/p\mathbb Z)^*$ always contain such a pair (Lemma 445.2).

(ii) First gap (crisp): Prove that for every fixed $c>1/2$ there is $p_0(c)$ such that for all primes $p\ge p_0(c)$ and all shifts $n$, the interval $(n,n+p^c)$ contains some $a$ with $a^{-1}$ also in the interval.

(iii) Top 3 next moves: 1. Reduce to bounding intersections $I\cap I^{-1}$ for additive intervals $I$ modulo $p$ of length $\lfloor p^c\rfloor$, uniformly in the shift, and attempt to show a uniform lower bound $|I\cap I^{-1}|\ge 1$. 2. Use exponential sum technology: express $|I\cap I^{-1}|$ via additive characters and attempt to bound the relevant bilinear/Kloosterman-type sums (this aligns with the methods cited in the problem statement). 3. Computation: for increasing primes $p$, compute the maximal "bad" shift $n$ for which $I_{n,p,c}\cap I_{n,p,c}^{-1}=\varnothing$ at various $c$ to look for sharp transition phenomena.

(iv) What a minimal counterexample would likely look like: a sequence of primes $p_j\to\infty$ and shifts $n_j$ such that the residue block corresponding to $(n_j,n_j+p_j^c)$ has empty intersection with its inverse image in $\mathbb F_{p_j}^*$, i.e. $I\cap I^{-1}=\varnothing$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Is it true that, for any $c>1/2$, if $p$ is a sufficiently large prime then, for any $n\geq 0$, there exist $a,b\in(n,n+p^c)$ such that $ab\equiv 1\pmod{p}$? Heilbronn (unpublished) proved this for $c$ sufficiently close to $1$. Heath-Brown [He00] used Kloosterman sums to prove this for all $c>3/4$. This is discussed in this MathOverflow question . References [He00] Heath-Brown, D. R., Arithmetic applications of {K}loosterman sums . Nieuw Arch. Wiskd. $5$ $2000$, 380--384.

FORMAL RESTATEMENT

Fix a real $c>\tfrac12$. For a prime $p$ and integer $n\ge 0$, define the integer interval \[ I_{n,p,c}:=\{a\in\mathbb Z: n<a<n+p^c\}. \] Question: is it true that for every $c>\tfrac12$ there exists $p_0(c)$ such that for every prime $p\ge p_0(c)$ and every integer $n\ge 0$ there exist $a,b\in I_{n,p,c}$ with \[ ab\equiv 1\pmod p? \] Equivalently: does every length-$\asymp p^c$ interval contain an element whose multiplicative inverse modulo $p$ also lies in the same interval?

Stress points: - the threshold $c=1/2$ is natural because inversion is a permutation on $(\mathbb Z/p\mathbb Z)^*$ and "random" intersection heuristics suggest $p^c$ needs to exceed $\sqrt p$.

QUICK LITERATURE/CONTEXT CHECK

I do not use any results beyond those explicitly stated here: Heilbronn proved the statement for $c$ close to $1$, and Heath-Brown proved it for all $c>3/4$ using Kloosterman sums.

ATTACK PLAN

Proof track (elementary bounds): 1) Prove a necessary condition: if an interval length $L$ works uniformly for all shifts $n$, then necessarily $L\gtrsim \sqrt p$ by a counting argument. 2) Prove a trivial sufficient condition for very long intervals (e.g. length $>\tfrac{p-1}{2}$) using a pigeonhole argument in the multiplicative group.

Disproof track: Try to produce explicit primes $p$ and shifts $n$ where an interval of length $\lfloor p^c\rfloor$ avoids its inverse set; a counting argument suggests this should be possible when $c<1/2$.

I carry out $1$ and $2$ rigorously and perform a small computation of the minimal interval length that works for all shifts for primes $p\le 200$.

WORK

FAST REALITY CHECK (small primes). For each prime $p\le 200$, I computed the minimal integer $L=L(p)$ such that for every residue class shift $n\pmod p$, the set of residues represented by $\{n+1,\dots,n+L\}$ (excluding $0$) contains some $a$ with $a^{-1}$ also in the same set. The ratios $L/\sqrt p$ varied between about $0.89$ and $2.97$ in this range; the worst case up to $200$ was $p=131$ with $L=34$. Selected values:

5 2 0.8944271909999159
7 3 1.1338934190276817
11 5 1.507556722888818
13 6 1.6641005886756874
17 7 1.697749375254331
23 9 1.876629726513673
37 13 2.137186834969645
...
max ratio L/sqrt(p) up to 200: 2.970593792647529 at (131, 34, 2.970593792647529)

This supports (but does not prove) the heuristic that the critical scale is $\asymp \sqrt p$.

Lemma 445.1 (elementary $\sqrt p$ barrier for uniform-in-$n$ statements). Let $p$ be an odd prime and let $L$ be an integer with $1\le L\le p-1$. Suppose that for every residue class $n\in\mathbb Z/p\mathbb Z$ there exist integers $1\le i\le j\le L$ such that \[ (n+i)(n+j)\equiv 1\pmod p. \] Then necessarily \[ L(L+1)\ge p. \] In particular, if $L(L+1)<p$ then there exists $n\pmod p$ such that no such pair exists.

Proof. For each $n\in\mathbb Z/p\mathbb Z$, define \[ Y_n := \#\left\{(i,j): 1\le i\le j\le L\text{ and }(n+i)(n+j)\equiv 1\pmod p\right\}. \] By hypothesis, $Y_n\ge 1$ for every $n$, hence \begin{equation} \sum_{n\in\mathbb Z/p\mathbb Z} Y_n \ge p. \tag{1} \end{equation}

On the other hand, fix a pair $(i,j)$ with $1\le i\le j\le L$. The congruence \[(n+i)(n+j)\equiv 1\pmod p\] expands to a quadratic congruence in $n$: \[n^2 + (i+j)n + (ij-1)\equiv 0\pmod p. \] Over the field $\mathbb F_p$, a nonzero polynomial of degree $2$ has at most $2$ roots. (Here the polynomial is not identically zero because its leading coefficient is $1\not\equiv 0\pmod p$.) Therefore, for each fixed $(i,j)$ there are at most $2$ values of $n\in\mathbb Z/p\mathbb Z$ that satisfy the congruence.

Summing over all pairs $(i,j)$ gives \[ \sum_{n\in\mathbb Z/p\mathbb Z} Y_n \le 2\cdot \#\{(i,j): 1\le i\le j\le L\} =2\cdot \frac{L(L+1)}{2}=L(L+1). \tag{2} \] Combining $1$ and $2$ yields $p\le L(L+1)$, as claimed. $\Box$

Lemma 445.2 (very long intervals always work). Let $p$ be an odd prime and let $S\subseteq\mathbb F_p^*$ be any subset with $|S|>\tfrac{p-1}{2}$. Then $S\cap S^{-1}\ne\varnothing$, where $S^{-1}:=\{x^{-1}:x\in S\}$. Consequently, if an interval $I\subseteq\{1,2,\dots,p-1\}$ has length $>\tfrac{p-1}{2}$, then there exist $a,b\in I$ with $ab\equiv 1\pmod p$.

Proof. The inversion map $x\mapsto x^{-1}$ is a bijection of $\mathbb F_p^*$, hence $|S^{-1}|=|S|$. If $S\cap S^{-1}=\varnothing$, then \[|S\cup S^{-1}| = |S|+|S^{-1}| = 2|S| > p-1, \] which is impossible since $S\cup S^{-1}\subseteq\mathbb F_p^*$ has size at most $p-1$. Therefore $S\cap S^{-1}\ne\varnothing$.

For the interval consequence, take $S$ to be the set of residue classes represented by the interval (excluding $0$), and apply the first part: an element $a\in S\cap S^{-1}$ means $a\in S$ and $a^{-1}\in S$, i.e. two elements of the interval multiply to $1\pmod p$. $\Box$

VERIFICATION

- Lemma 445.1: The only nontrivial facts are (a) quadratic polynomials over a field have at most two roots, and (b) the polynomial is genuinely degree 2 because the coefficient of $n^2$ is $1$. Both are correct. - Lemma 445.2: uses only that inversion is a bijection. - Matching the original quantifiers: Lemma 445.1 addresses the uniform-in-$n$ requirement (for every shift). It provides a necessary condition $L\gtrsim\sqrt p$, aligning with the stated threshold $c>1/2$.

FINAL

UNRESOLVED

(i) Strongest proved partial result: For any prime $p$, if an interval length $L$ works for every shift $n$ (i.e. always contains $a,b$ with $ab\equiv1\pmod p$), then $L(L+1)\ge p$ (Lemma 445.1), giving an elementary $\sqrt p$ barrier. Also, intervals representing more than half of $(\mathbb Z/p\mathbb Z)^*$ always contain such a pair (Lemma 445.2).

(ii) First gap (crisp): Prove that for every fixed $c>1/2$ there is $p_0(c)$ such that for all primes $p\ge p_0(c)$ and all shifts $n$, the interval $(n,n+p^c)$ contains some $a$ with $a^{-1}$ also in the interval.

(iii) Top 3 next moves: 1. Reduce to bounding intersections $I\cap I^{-1}$ for additive intervals $I$ modulo $p$ of length $\lfloor p^c\rfloor$, uniformly in the shift, and attempt to show a uniform lower bound $|I\cap I^{-1}|\ge 1$. 2. Use exponential sum technology: express $|I\cap I^{-1}|$ via additive characters and attempt to bound the relevant bilinear/Kloosterman-type sums (this aligns with the methods cited in the problem statement). 3. Computation: for increasing primes $p$, compute the maximal "bad" shift $n$ for which $I_{n,p,c}\cap I_{n,p,c}^{-1}=\varnothing$ at various $c$ to look for sharp transition phenomena.

(iv) What a minimal counterexample would likely look like: a sequence of primes $p_j\to\infty$ and shifts $n_j$ such that the residue block corresponding to $(n_j,n_j+p_j^c)$ has empty intersection with its inverse image in $\mathbb F_{p_j}^*$, i.e. $I\cap I^{-1}=\varnothing$.