gpt pro 5.2 attempt on Math-817

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$.