Erdős Problem #1163

Erdős Problem 1163 --- GPT 6 Astra Ultra partial attempt

FORMAL RESTATEMENT

Study, using statistical descriptions, the arithmetic properties of the orders of subgroups $|H|$ with $H\leq S_n$ as $n$ varies.

CONTEXT AND SCOPE

This replaces the earlier statement-only record with an elementary mathematical attempt. The arguments below establish only their stated partial results; no novelty or full solution is claimed.

The official page explicitly calls the intended meaning unclear. It does not choose between statistics of distinct attainable orders, a uniformly sampled subgroup, or a randomly generated subgroup. This attempt preserves that ambiguity.

ATTACK PLAN AND WORK

To expose the statistical-model issue quantitatively, consider the concrete family $E\cong\mathbb F_2^k\le S_{2k}$ generated by disjoint transpositions. It has exactly $k+1$ distinct subgroup orders, namely $2^j$ for $0\le j\le k$. Uniform sampling of these orders makes $j$ uniform. Uniform sampling of its subgroups gives a quite different distribution.

Counting ordered bases of subspaces gives \[N_{k,j}=\prod_{i=0}^{j-1}\frac{2^k-2^i}{2^j-2^i},\qquad 2^{j(k-j)}\le N_{k,j}\le4\,2^{j(k-j)}.\tag{1}\] For the upper bound, the denominator after normalization is $\prod_{h=1}^j(1-2^{-h})\ge1/4$: the first two factors give $3/8$, and the remaining product is at least $1-\sum_{h\ge3}2^{-h}=3/4$. The lower bound follows by comparing each normalized numerator factor with the corresponding denominator factor.

Since there are at least $2^{\lfloor k^2/4\rfloor}$ subgroups in total, uniform subgroup sampling satisfies \[\Pr(|j-k/2|\ge t)\le4(k+1)2^{-t^2+1/4}.\tag{2}\] Thus this distribution is concentrated near the middle rank, unlike uniform sampling of the distinct attainable orders. Equations $1$--$2$ concern subgroups of $E$, not all subgroups of $S_{2k}$; that restriction is essential.

VERIFICATION AND REMAINING GAP

Fix the intended sampling rule, then analyze the full symmetric-group subgroup family. The example proves that two natural interpretations need not have the same answer; it does not choose the intended interpretation for the source.

SOURCES

https://www.erdosproblems.com/1163

https://www.erdosproblems.com/forum/thread/1163

FINAL

UNRESOLVED. The full source problem remains outside the scope of the proved partial results.

COMPLETION ESTIMATE

$5\%$. This is a conservative subjective estimate toward the whole problem, not a probability that the argument is correct or a claim that a fixed fraction of the problem has been solved.