Erdős Problem #475

Erdős Problem #475: collision counting, a greedy barrier and an exact sequencing audit

1) Formal restatement and source check

The current problem page, fetched 23 September 2026, lists this as DECIDABLE. It records the combined results for all sufficiently large primes, but not a complete treatment of every remaining prime. We do not replace the finite remainder by an assertion that the large-prime theorem proves all cases. The older local attempt gives geometric-progression examples and only a partial computational audit at $p=17$. Here we supply different elementary criteria and complete, reproducible checks of every subset for every prime through 19. No literature novelty is claimed for the criteria or for these small instances.

2) A collision-counting sufficient condition

The exclusion of the first-position block is essential. Counting all $t-r+1$ blocks would concern a stronger condition involving $s_0$, and could discard valid orderings. A zero sum of the entire set causes no collision by itself.

A deterministic special case. If there exists $x\in A$ such that $A\setminus\{x\}$ has no nonempty zero-sum subset, put $x$ first and arrange the rest arbitrarily. Any collision would give a nonempty zero-sum block entirely inside the suffix, which is impossible. This criterion remains valid even if the total sum of $A$ is zero. It is sufficient, not necessary.

Condition $1$ also illustrates its own limitation: if the sum is at least one, the first-moment argument says nothing. A large average collision count does not imply that every ordering has a collision. We have not bounded the $Z_r(A)$ sharply enough for arbitrary $A$ to make $1$ universal.

3) What greedy extension always achieves

Proof. Suppose a greedy construction has already used $k$ elements and its sums $s_1,\ldots,s_k$ are distinct. An unused nonzero $a$ is forbidden precisely when $s_k+a=s_i$ for some $i\leq k$. The value $i=k$ would require $a=0$, so at most $k-1$ unused values are forbidden. If $t-k>k-1$, at least one extension is available. Consequently a maximal greedy construction has $k\geq\lceil(t+1)/2\rceil=\lfloor t/2\rfloor+1$. $\square$

In the tight odd case $t=2m+1$ and $k=m+1$, a blocked construction must have remaining set exactly \[ A\setminus\{a_1,\ldots,a_k\}=\{s_i-s_k:1\leq i<k\}. \tag{2} \] Both sides have $k-1$ elements and the forbidden values are distinct, proving the equality. This is a useful description of a failed search branch, not a contradiction.

For example, in $\mathbb F_7$, take $A=\{1,2,5\}$. Starting with $1,2$ gives sums $1,3$, and adding 5 repeats 1. But the ordering $2,1,5$ has sums $2,3,1$ and succeeds. Thus a blocked greedy branch cannot certify a counterexample, even in the smallest tight case. A complete search must backtrack or make a separately justified rearrangement.

4) Completed exhaustive finite audit

Two safe pruning rules are used. First, repeated partial sums are forbidden. Second, the final sum $S=\sum_{a\in A}a$ is fixed independently of ordering; a partial sum at a nonfinal position may not equal $S$, since the final step would then repeat it. Failed states are memoized by the remaining elements and visited sums. The current sum is determined by the remaining elements as $S-\sum_{a\text{ remaining}}a$, so this memoization does not conflate inequivalent states. Crucially, the visited set is initially empty, not $\{0\}$.

The completed report verification/add_475_checks.json records: \[ \begin{array}{c|r} p&\text{all subsets checked}\\ 2&2\\3&4\\5&16\\7&64\\11&1024\\13&4096\\17&65536\\19&262144 \end{array} \] All 332886 subsets have verified valid orderings. This completes the small-prime range that the earlier local text did not finish, but is not presented as progress beyond the published small-parameter results. The prime $p=2$ is handled directly by the same program, avoiding division by $g-1$ in geometric-progression arguments when $g=1$.

5) Adversarial verification and remaining gap

6) Final

7) References

The estimate is subjective. It measures the limited scope of this partial attempt, not the fraction of all primes checked and not a probability that the conjecture is true.

8) COMPLETION ESTIMATE

1) “FORMAL RESTATEMENT”

Let p be a prime and let A be any finite subset of F_p {0}. Write |A|=t. The question is whether there always exists an ordering $a_1,...,a_t$ of the elements of A such that the partial sums

s_m := a_1 + a_2 + ... + a_m (mod p)

are pairwise distinct for all 1<=m<=t.

Equivalently: the walk starting at 0 and taking steps a_1,...,a_t visits t distinct vertices of the cyclic group F_p.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement lists several partial results (t<=12; p-3<=t<=p-1; and various growing ranges). A quick check of the Erdos Problems page for #475 shows it is listed as OPEN (as of mid-Jan 2026). I do not use any external results beyond the problem statement.

3) “ATTACK PLAN”

- Prove the conjecture for special structured sets A (e.g. geometric progressions), to understand mechanisms. - Search for counterexamples by brute force for small primes p and all subsets A. - For a general proof, one expects a mix of additive combinatorics and an “absorption”/rearrangement argument to fix collisions of partial sums.

4) “WORK”

Proposition 475.1 (full set A = F_p^* has a valid ordering). Let g be a primitive root modulo p (so g has multiplicative order p-1). Consider the ordering

a_1=1, a_2=g, a_3=g^2, ..., a_{p-1}=g^{p-2}.

Then the partial sums s_m are all distinct (for 1<=m<=p-1).

Proof. For m>=1, we have a geometric series identity in F_p:

s_m = 1 + g + g^2 + ... + g^{m-1} = $g^m - 1$/$g - 1$,

where division by $g-1$ is valid because g!=1. Suppose s_m = s_n for some 1<=m,n<=p-1. Multiply by $g-1$: g^m - 1 = g^n - 1, hence g^m = g^n. Since g has order p-1 and 1<=m,n<=p-1, this forces m=n. Thus the partial sums are pairwise distinct. QED.

Proposition 475.2 (geometric progression sets). Let A = {1, g, g^2, ..., g^{t-1}} be a geometric progression in F_p^* with g!=1, and assume t <= ord(g) (so the listed powers are distinct). Then the same ordering a_j = g^{j-1} has distinct partial sums.

Proof. The same computation gives s_m = $g^m - 1$/$g - 1$. If s_m=s_n then g^m=g^n, and since 0<=m-1,n-1<=t-1 < ord(g), we get m=n. QED.

FAST REALITY CHECK (local computation). I brute-forced the conjecture for small primes by checking every subset A of F_p^* and testing whether some permutation gives distinct partial sums.

- For p in {3,5,7,11,13}, every subset A ⊆ F_p^* admits a valid ordering (no counterexamples). - For p=17, I checked all subsets of sizes up to 9 (inclusive) and found no counterexample in that range. (The full p=17 check over all 2^16 subsets is heavier; the computation above was cut off by time limits before completing size 10 and above.)

5) “VERIFICATION”

- Proposition 475.1 produces an explicit valid ordering for the extremal case t=p-1 (matching the partial result mentioned in the problem statement). - The proof uses only that g has order p-1 (primitive root) and g!=1. - In Proposition 475.2, the hypothesis t<=ord(g) is needed so that g^m=g^n implies m=n for exponents in {1,...,t}.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: The conjecture holds when A is the full multiplicative group F_p^* (explicit ordering via powers of a primitive root), and more generally for any geometric progression A={1,g,...,g^{t-1}} with t<=ord(g).

(ii) First gap (crisp statement): Prove (or find a counterexample to) the statement: every subset A ⊆ F_p^* has some ordering with distinct partial sums.

(iii) Top 3 next moves (concrete): 1. Try to extend Proposition 475.2 from geometric progressions to sets A with small multiplicative doubling (A·A small), via Freiman-type structure plus a rearrangement/absorption step. 2. Attempt a probabilistic construction: show that a random ordering has few collisions of partial sums and then repair collisions locally. 3. Systematically search for counterexamples in the “middle range” of sizes, say t around p/2, for moderately large primes $e.g. p~200-500$, using backtracking with pruning.

(iv) Minimal counterexample structure (if the answer is “no”): A prime p and a subset A ⊆ F_p^* such that for every permutation $a_1,...,a_t$, two distinct partial sums coincide, i.e. there exist 1<=m<n<=t with a_1+...+a_m ≡ a_1+...+a_n (mod p).