Erdős Problem #478

Erdős Problem 478 --- collection record

PROVENANCE AND STATUS

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/478.tex.

REUSED SOURCE 1

1) “FORMAL RESTATEMENT”

Let p be a prime. Define

A_p := { k! (mod p) : 1 <= k < p } ⊆ F_p.

Question: Is it true that |A_p|   $1 - 1/e$ p as p -> infinity?

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement records the conjecture |A_p|   $1-1/e$p and some remarks (e.g. A_p/A_p = F_p^* and |A_p|<=p-2). A quick check of the Erdos Problems page for #478 shows it is listed as OPEN (as of mid-Jan 2026). I do not use external results beyond standard modular arithmetic.

3) “ATTACK PLAN”

Prove basic structural facts about A_p (ratio set, unavoidable collisions from Wilson's theorem, etc.). Then do computations for many primes to see whether |A_p|/p stabilizes near 1-1/e.

A proof of the conjecture would require a probabilistic model for when the recurrence k! mod p repeats.

4) “WORK”

Lemma 478.1 (ratio set is everything nonzero). For any prime p, we have A_p / A_p = F_p^*.

Proof. Fix any x in F_p^* (so x is represented by an integer 1<=x<=p-1). Then

x ≡ x! / $x-1$! (mod p).

Both x! and $x-1$! occur among k! for 1<=k<p (note that for x=1, we can use 1!/1!=1). Hence x belongs to A_p/A_p. Therefore A_p/A_p contains every nonzero residue. QED.

Lemma 478.2 (trivial lower bound). |A_p| >= sqrt$p-1$.

Proof. In any finite group, |X/Y| <= |X| |Y|, and in particular |A_p/A_p| <= |A_p|^2. By Lemma 478.1, |A_p/A_p| = |F_p^*| = p-1. Hence p-1 <= |A_p|^2, i.e. |A_p| >= sqrt$p-1$. QED.

Lemma 478.3 (Wilson collision gives |A_p|<=p-2, and p≡3 (mod 4) forces |A_p|<=p-3).

(a) For any prime p, we have |A_p| <= p-2. (b) If p ≡ 3 (mod 4), then |A_p| <= p-3. In particular, if |A_p|=p-2 then necessarily p ≡ 1 (mod 4).

Proof. (a) By Wilson's theorem, $p-1$! ≡ -1 (mod p). Then

$p-2$! ≡ $p-1$! * $p-1$^{-1} ≡ $-1$ * $-1$ ≡ 1 (mod p),

since $p-1$ ≡ -1 and its inverse is also -1 modulo p. But 1! ≡ 1 as well. Thus at least two distinct k (namely k=1 and k=p-2) yield the same residue 1, so among the p-1 factorial values there is at least one repetition, hence |A_p| <= $p-1$ - 1 = p-2.

(b) Let h = $p-1$/2. Consider h! modulo p. We compute

$p-1$! = $1*2*...*h$ * $(h+1)*...*(p-1)$.

In the second product, substitute k -> p-k to pair terms: $h+1$*...*$p-1$ ≡ $-1$^h * $1*2*...*h$ (mod p). Therefore

$p-1$! ≡ $-1$^h * (h!)^2 (mod p).

By Wilson, $p-1$! ≡ -1, so (h!)^2 ≡ $-1$^{h+1} (mod p). If p ≡ 3 (mod 4), then h=$p-1$/2 is odd, so h+1 is even and $-1$^{h+1}=+1. Hence (h!)^2 ≡ 1 (mod p), so h! ≡ 1 or h! ≡ -1 (mod p).

- If h! ≡ 1, then the residue 1 occurs at k=1, k=h, and k=p-2 (at least three occurrences), so |A_p| <= $p-1$ - 2 = p-3. - If h! ≡ -1, then the residue -1 occurs at k=h and k=p-1, while 1 occurs at k=1 and k=p-2, giving at least two distinct repetitions, again |A_p| <= p-3.

Thus for p≡3 (mod 4) we cannot have |A_p|=p-2. Therefore, if |A_p|=p-2 then p must be ≡1 (mod 4). QED.

FAST REALITY CHECK (local computation). I computed |A_p| exactly for all primes p<=10000. Summary:

- Number of odd primes p<=10000 tested: 1228. - Mean of |A_p|/p over these primes: 0.6319266077934649. - Median of |A_p|/p over these primes: 0.6323326214052672. - For comparison, 1 - 1/e = 0.6321205588285577. - The only prime p<=10000 with |A_p|=p-2 is p=5.

5) “VERIFICATION”

- Lemma 478.1 is verified directly by the identity x = x!/$x-1$! in F_p. - Lemma 478.3(b) uses only Wilson's theorem and the simple pairing argument in the product $h+1$...$p-1$. - The computation of |A_p| uses the recurrence fac_{k+1} = fac_k*$k+1$ (mod p) and counts distinct residues.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: We have the universal bounds sqrt$p-1$ <= |A_p| <= p-2, and if p≡3 (mod 4) then |A_p| <= p-3. Computationally, |A_p|/p for p<=10000 has mean 0.6319266..., extremely close to 1-1/e.

(ii) First gap (crisp statement): Prove that |A_p|/p converges and identify the limit; in particular, prove or disprove lim_{p->infty} |A_p|/p = 1 - 1/e.

(iii) Top 3 next moves (concrete): 1. Model the recurrence k! mod p as a random walk on F_p^* with multipliers k, and try to justify a Poisson-collision heuristic leading to 1-1/e. 2. Prove nontrivial upper and lower bounds of the form c p <= |A_p| <= C p with explicit constants c,C close to 1-1/e. 3. Study the distribution of first collision times: analyze the smallest k<l with k!≡l! (mod p), i.e. $k+1$$k+2$...l ≡ 1 (mod p).

(iv) Minimal counterexample structure (if the conjecture is false): A sequence of primes p_j -> infinity such that |A_{p_j}|/p_j stays bounded away from 1-1/e by some fixed epsilon>0.

COMPLETION ESTIMATE

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

1) “FORMAL RESTATEMENT”

Let p be a prime. Define

A_p := { k! (mod p) : 1 <= k < p } ⊆ F_p.

Question: Is it true that |A_p|   $1 - 1/e$ p as p -> infinity?

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement records the conjecture |A_p|   $1-1/e$p and some remarks (e.g. A_p/A_p = F_p^* and |A_p|<=p-2). A quick check of the Erdos Problems page for #478 shows it is listed as OPEN (as of mid-Jan 2026). I do not use external results beyond standard modular arithmetic.

3) “ATTACK PLAN”

Prove basic structural facts about A_p (ratio set, unavoidable collisions from Wilson's theorem, etc.). Then do computations for many primes to see whether |A_p|/p stabilizes near 1-1/e.

A proof of the conjecture would require a probabilistic model for when the recurrence k! mod p repeats.

4) “WORK”

Lemma 478.1 (ratio set is everything nonzero). For any prime p, we have A_p / A_p = F_p^*.

Proof. Fix any x in F_p^* (so x is represented by an integer 1<=x<=p-1). Then

x ≡ x! / $x-1$! (mod p).

Both x! and $x-1$! occur among k! for 1<=k<p (note that for x=1, we can use 1!/1!=1). Hence x belongs to A_p/A_p. Therefore A_p/A_p contains every nonzero residue. QED.

Lemma 478.2 (trivial lower bound). |A_p| >= sqrt$p-1$.

Proof. In any finite group, |X/Y| <= |X| |Y|, and in particular |A_p/A_p| <= |A_p|^2. By Lemma 478.1, |A_p/A_p| = |F_p^*| = p-1. Hence p-1 <= |A_p|^2, i.e. |A_p| >= sqrt$p-1$. QED.

Lemma 478.3 (Wilson collision gives |A_p|<=p-2, and p≡3 (mod 4) forces |A_p|<=p-3).

(a) For any prime p, we have |A_p| <= p-2. (b) If p ≡ 3 (mod 4), then |A_p| <= p-3. In particular, if |A_p|=p-2 then necessarily p ≡ 1 (mod 4).

Proof. (a) By Wilson's theorem, $p-1$! ≡ -1 (mod p). Then

$p-2$! ≡ $p-1$! * $p-1$^{-1} ≡ $-1$ * $-1$ ≡ 1 (mod p),

since $p-1$ ≡ -1 and its inverse is also -1 modulo p. But 1! ≡ 1 as well. Thus at least two distinct k (namely k=1 and k=p-2) yield the same residue 1, so among the p-1 factorial values there is at least one repetition, hence |A_p| <= $p-1$ - 1 = p-2.

(b) Let h = $p-1$/2. Consider h! modulo p. We compute

$p-1$! = $1*2*...*h$ * $(h+1)*...*(p-1)$.

In the second product, substitute k -> p-k to pair terms: $h+1$*...*$p-1$ ≡ $-1$^h * $1*2*...*h$ (mod p). Therefore

$p-1$! ≡ $-1$^h * (h!)^2 (mod p).

By Wilson, $p-1$! ≡ -1, so (h!)^2 ≡ $-1$^{h+1} (mod p). If p ≡ 3 (mod 4), then h=$p-1$/2 is odd, so h+1 is even and $-1$^{h+1}=+1. Hence (h!)^2 ≡ 1 (mod p), so h! ≡ 1 or h! ≡ -1 (mod p).

- If h! ≡ 1, then the residue 1 occurs at k=1, k=h, and k=p-2 (at least three occurrences), so |A_p| <= $p-1$ - 2 = p-3. - If h! ≡ -1, then the residue -1 occurs at k=h and k=p-1, while 1 occurs at k=1 and k=p-2, giving at least two distinct repetitions, again |A_p| <= p-3.

Thus for p≡3 (mod 4) we cannot have |A_p|=p-2. Therefore, if |A_p|=p-2 then p must be ≡1 (mod 4). QED.

FAST REALITY CHECK (local computation). I computed |A_p| exactly for all primes p<=10000. Summary:

- Number of odd primes p<=10000 tested: 1228. - Mean of |A_p|/p over these primes: 0.6319266077934649. - Median of |A_p|/p over these primes: 0.6323326214052672. - For comparison, 1 - 1/e = 0.6321205588285577. - The only prime p<=10000 with |A_p|=p-2 is p=5.

5) “VERIFICATION”

- Lemma 478.1 is verified directly by the identity x = x!/$x-1$! in F_p. - Lemma 478.3(b) uses only Wilson's theorem and the simple pairing argument in the product $h+1$...$p-1$. - The computation of |A_p| uses the recurrence fac_{k+1} = fac_k*$k+1$ (mod p) and counts distinct residues.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: We have the universal bounds sqrt$p-1$ <= |A_p| <= p-2, and if p≡3 (mod 4) then |A_p| <= p-3. Computationally, |A_p|/p for p<=10000 has mean 0.6319266..., extremely close to 1-1/e.

(ii) First gap (crisp statement): Prove that |A_p|/p converges and identify the limit; in particular, prove or disprove lim_{p->infty} |A_p|/p = 1 - 1/e.

(iii) Top 3 next moves (concrete): 1. Model the recurrence k! mod p as a random walk on F_p^* with multipliers k, and try to justify a Poisson-collision heuristic leading to 1-1/e. 2. Prove nontrivial upper and lower bounds of the form c p <= |A_p| <= C p with explicit constants c,C close to 1-1/e. 3. Study the distribution of first collision times: analyze the smallest k<l with k!≡l! (mod p), i.e. $k+1$$k+2$...l ≡ 1 (mod p).

(iv) Minimal counterexample structure (if the conjecture is false): A sequence of primes p_j -> infinity such that |A_{p_j}|/p_j stays bounded away from 1-1/e by some fixed epsilon>0.