GPT 6 Astra Ultra attempt on Math-5725

Erdős problem 543. Let $f(N)$ be the least $k$ such that, in every abelian group of order $N$, a uniformly chosen $k$-element subset spans the group by subset sums with probability at least $1/2$. Is $f(N)\leq\log_2N+o(\log\log N)$?

Status and attribution. No. The following reconstructs the rank-counting and moment argument of Quanyu Tang and ChatGPT-5.2 Pro, A note on problem #543, revised 23 January 2026: https://github.com/QuanyuTang/erdos-problem-543/blob/main/On_Erdos_Problem_543_Revised_and_Verified.pdf. The current problem page is https://www.erdosproblems.com/543, checked 24 September 2026. This is an exposition of that existing argument; the filename of the source is not a claim that this file has been formally verified.

Reduction to independent sampling. Let $p$ tend to infinity through primes, and let $k=\log_2p+o(\log\log p)$ be integral. Sample $a_1,\ldots,a_k$ independently and uniformly from $\mathbb F_p$. The probability of any repetition is at most $\binom k2/p=o(1)$. Conditional on no repetitions, the underlying set is a uniformly random $k$-subset. It therefore suffices to show that the indexed subset sums fail to cover $\mathbb F_p$ with probability tending to one.

Put $M=2^k-1$, $\lambda=M/p$, and $R=\lfloor(\log p)^{1/3}\rfloor$, with natural logarithms except where a base is displayed. Then \[ M=p^{1+o(1)},\qquad \lambda=(\log p)^{o(1)},\qquad \lambda=o(R),\qquad \lambda=o(\log p). \tag{1} \] For $B\subseteq\mathbb F_p$ with $m=|B|\in\{1,2\}$, let $X_B$ count pairs $(S,b)$ with $\varnothing\ne S\subseteq[k]$, $b\in B$, and $\sum_{i\in S}a_i=b$. We will prove uniformly over these target sets that \[ \mathbb P(X_B=0)=e^{-m\lambda}(1+o(1)). \tag{2} \]

Counting dependent patterns. For $r\leq R+1$, a list of distinct nonempty subsets $S_1,\ldots,S_r$ defines a binary incidence matrix $V$ of size $r$ by $k$. Let its rank be $d$. Its rational rank agrees with its rank modulo $p$ for all sufficiently large $p$: every nonzero minor has absolute determinant at most $r^{r/2}<p$, by Hadamard's bound. The equations $Va=b$ consequently have probability either zero or $p^{-d}$, according as $b$ lies outside or inside the image.

We need the following elementary cube bound. If the binary rows of $V$ are nonzero and distinct and $d<r$, its column space $W\subseteq\mathbb Q^r$ satisfies \[ |W\cap\{0,1\}^r|\leq(3/4)2^d. \tag{3} \] Choose $d$ coordinate positions giving an isomorphism $W\to\mathbb Q^d$. Each remaining coordinate is a homogeneous linear form in these $d$ coordinates. At least one such form has at least two nonzero coefficients: a zero form would force a zero row, and a form using just one coordinate would make two nonzero binary rows proportional, hence identical. For a form with two nonzero coefficients $a,b$, condition on its other inputs. The four equally likely values are $C,C+a,C+b,C+a+b$. They cannot all belong to $\{0,1\}$: if the first three do, nonzero $a,b$ must both be $1$ or both be $-1$, making the fourth leave that set. Thus at most three inputs work. This proves $3$.

There are at most $2^{rd}\leq2^{r^2}$ possible column spaces of rank $d$, since such a space has a basis of $d$ binary columns. Once the space is fixed, $3$ gives at most $((3/4)2^d)^k$ matrices. Therefore the number of ordered lists of distinct nonzero rows having rank $d<r$ is at most \[ 2^{r^2}(3/4)^k2^{dk}. \tag{4} \]

Uniform factorial moments. The factorial moment $\mathbb E(X_B)_r$ sums joint probabilities over ordered lists of distinct pairs $(S_i,b_i)$. If a subset repeats, its two targets must differ, so the equations are inconsistent. The number of these repeated-subset lists is at most $O(r^2m^rM^{r-1})$. For distinct subsets, every full-rank list contributes exactly $p^{-r}$. For deficient rank, $4$, with at most $m^r$ target assignments, bounds the total contribution by \[ m^r2^{r^2}(3/4)^k \sum_{d<r}(2^k/p)^d=p^{-\eta_0+o(1)},\qquad \eta_0=\log_2(4/3)>0. \tag{5} \] Here $r^2=o(\log p)$, and uniformly $d\leq R+1$, $d|\log(2^k/p)|=o(\log p)$. The same bound controls the full-rank baseline contribution erroneously assigned to these deficient lists, because $p^{-r}\leq p^{-d}$. The repeated-subset baseline is $O(r^2m^rM^{r-1}p^{-r})=p^{-1+o(1)}$. Finally \[ (mM)_r/p^r=(m\lambda)^r+O(p^{-1+o(1)}) \] uniformly, by the product expansion of the falling factorial and $r^2/M=o(1)$. Hence some absolute $\eta>0$ satisfies, uniformly for $1\leq r\leq R+1$ and all one- or two-point target sets, \[ \mathbb E(X_B)_r=(m\lambda)^r+O(p^{-\eta}). \tag{6} \]

From moments to missing targets. Bonferroni's inequalities bound $\mathbb P(X_B=0)$ between successive even and odd truncations of $\sum_r(-1)^r\mathbb E(X_B)_r/r!$. Using truncation orders $R$ and $R+1$, $6$ gives error $O(p^{-\eta})$, since $\sum1/r!\leq e$. The corresponding Taylor sums differ from $e^{-m\lambda}$ by at most $(m\lambda)^{R+1}/(R+1)!$ and its next-order analogue. These are $o(e^{-m\lambda})$: by $1$, their logarithms are at most $-(R+1)\log((R+1)/(em\lambda))$, whose magnitude dominates $\lambda$. Also $p^{-\eta}=o(e^{-m\lambda})$ because $\lambda=o(\log p)$. This proves $2$.

The second moment finishes the disproof. Let $U$ count the nonzero residues missed by all nonempty indexed subset sums. Formula $2$ gives \[ \mathbb EU=(p-1)e^{-\lambda}(1+o(1))\longrightarrow\infty, \] \[ \mathbb E[U(U-1)]=(p-1)(p-2)e^{-2\lambda}(1+o(1)). \] Thus $\operatorname{Var}U/(\mathbb EU)^2=o(1)$, and Chebyshev gives $\mathbb P(U=0)=o(1)$. Coverage includes every nonzero residue, so its probability is $o(1)$. Conditioning on the no-repetition event changes this limit by $o(1)$, establishing the same failure probability for a uniformly random $k$-subset.

Finally coverage probability is nondecreasing in the subset size, by sampling a random ordering and taking its successive initial sets. If the proposed upper bound for $f(p)$ held, enlarging to an integer $k=\log_2p+o(\log\log p)$ at least $f(p)$ would give coverage probability at least $1/2$, contradicting what was just proved.

Completion estimate. The prime-order counterexample, uniform missing-target estimate, and sampling conversion are all reconstructed above. COMPLETION: 100%