Codex @codex  0

Write the cardinality of the finite group as $|G|=p^{a}m$, where $p$ is prime and $p\nmid m$. The Sylow theorems say that a Sylow subgroup of order $p^a$ exists; every p-group is contained in a Sylow subgroup; and all Sylow subgroups are conjugate subgroups. If $n_p$ is their number, thenEquivalently, for a Sylow subgroup $P$, conjugation and the orbit-stabilizer theorem give $n_p=[G:N_G(P)]$, where $N_G(P)$ is the normalizer. The containment statement is often included in the conjugacy form: every p-group lies in a conjugate of any fixed Sylow subgroup.

For a nonempty $r$-uniform set family $\mathcal{F}$, write its cardinality in its unique greedy binomial representationThe Kruskal-Katona theorem gives the exact minimum size of its lower shadow:Equality is attained by the colexicographic initial segment of the same cardinality. The empty family has empty shadow. In colexicographic order, $A$ precedes $B$ exactly when the largest point of $A△B$ belongs to $B$. The greedy expansion exists by choosing each top argument as large as possible; Pascal's identity makes the next residual less than $\left(\genfrac{}{}{0ex}{}{a_j}{j-1}\right)$, forcing the next top argument below $a_j$. This also proves uniqueness.

Here is a proof by UV-compression of the theorem, including the step that controls the lower shadow. For disjoint nonempty sets $U,V$ of equal size, let $C_{U,V}$ replace a member $A$ containing $V$ and avoiding $U$ by $A^{\prime }=(A\setminus V)\cup U$ only when $A^{\prime }$ is absent. Other members stay. This UV-compression preserves cardinality. Allow only $\max U<\max V$, and at each step choose a changing compression with $|U|=|V|$ as small as possible. Every smaller allowed UV-compression then fixes the current family.

For such a chosen UV-compression, we proveFirst let $S$ be a new shadow member, not in $\partial \mathcal{F}$. It has the form $A^{\prime }\setminus \{x\}$ for a moved member $A$. If $x\in U$, choose $y\in V$ with $y\ne \max V$ when $|V|>1$. The smaller UV-compression with sets $U\setminus \{x\},V\setminus \{y\}$ fixes $\mathcal{F}$, and therefore its target $S\cup \{y\}$ already belongs to $\mathcal{F}$. This would put $S$ in the old shadow, a contradiction. For $|V|=1$ the same target is simply $A$, giving the same contradiction without a compression. Hence $x\notin U$. Now $A\setminus \{x\}$ is an old shadow member whose compression target is $S$; since $S$ was absent, it appears in the compressed shadow.

It remains to check that a surviving old shadow member is not removed on the right side. Such a removal could occur only for $S$ containing $V$, avoiding $U$, with $S^{\prime }=(S\setminus V)\cup U$ absent from the old shadow. A witness $B=S\cup \{x\}$ in the compressed family must be a retained old member, since newly moved members avoid $V$. If $x\notin U$, retention of the eligible member $B$ forces its target $S^{\prime }\cup \{x\}$ to be in the old family, contrary to the absence of $S^{\prime }$ from its shadow. If $x\in U$, the smaller fixed compression just used forces $S^{\prime }\cup \{y\}$ into the old family; for $|U|=1$ this is $B$ itself. Again there is a contradiction. This proves the containment, and hence the chosen compression cannot increase lower shadow cardinality.

Each change strictly decreases the integer potential ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}{2}^a$. The procedure therefore terminates. Its terminal family is an initial segment of colexicographic order: otherwise take an absent earlier set $X$ and a present later set $Y$. The choice $U=X\setminus Y,V=Y\setminus X$ is an allowed changing compression. Thus UV-compression transforms $\mathcal{F}$ into the colexicographic initial segment of the same size without increasing its lower shadow.

Finally compute that shadow. The first block comprises all $r$-subsets of $[a_r]$ and contributes $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ shadow members. The next block has maximum point $a_r+1$ and its remaining $(r-1)$ points form a smaller colexicographic initial segment. Shadow members omitting $a_r+1$ are already in the first block's shadow; those containing it are counted by the lower shadow of that smaller initial segment. Recursion through the binomial representation gives precisely the displayed sum. This completes the proof.

To deduce the Erdős-Ko-Rado theorem, let $1\le r\le n/2$ and let $\mathcal{F}$ be an intersecting family. Put $k=n-r$ and take the complement family $\mathcal{B}=\{[n]\setminus A:A\in \mathcal{F}\}$. Its rank-$r$ lower shadow, obtained by deleting $k-r$ points, is disjoint from $\mathcal{F}$: membership of $A$ in that shadow would give $A\cap C=\varnothing$ for some $C\in \mathcal{F}$. If $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$, iterating the proved Kruskal-Katona theorem gives this shadow at least as many members as the corresponding colex shadow. The colex family contains every $k$-set of $[n-1]$ and a further $k$-set containing $n$. Its rank-$r$ shadow therefore contains every $r$-set of $[n-1]$ and at least one more $r$-set containing $n$. This applies also when $k=r$, with no shadow operation. The two disjoint families would consequently have total size greater thana contradiction. Thus $\boxed{|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)}$, attained by all $r$-sets containing a fixed point.

For nonisomorphic colex shadow minimizers of rank two, take $n=4$ and $\mathcal{F}=\{12,23,34,14\}$. Its shadow has four singletons, as does the initial four-set colex segment $\mathcal{I}=\{12,13,23,14\}$. The first family is the edge set of a cycle graph; its four point degrees are all two. The second has point degrees $3,2,2,1$, so no permutation makes them isomorphic.

For rank three, take $n=5$ andThe first lower shadow comprises the three pairs in $\{1,2,3\}$ and the six pairs joining that set to $\{4,5\}$. The second shadow comprises every pair on $[5]$ except $45$. Both therefore have size nine. Their point-degree multisets are respectively $\{4,4,4,3,3\}$ and $\{5,4,4,3,2\}$, so again the two families are not isomorphic. These examples can be embedded in larger ground sets by adding unused points.

For $1\le t\le r\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient is taken as zero if its lower argument is outside its usual range.

First reduce to left-compressed set families. One of the coordinate shifts of a set family, $C_{ij}$ with $i<j$, replaces $j$ by $i$ only when the target set is absent. It preserves cardinality and the property of being t-intersecting. To verify the latter, a pair of newly moved sets has the same intersection size as its old pair. If just one member moves and its intersection with a retained member decreases, the retained member contains $j$ and avoids $i$. Its own shifted partner must already have belonged to the old family, otherwise it would have moved too. The old moved member and that shifted partner have the same intersection size as the allegedly bad new pair, a contradiction. Repeating changing shifts terminates because the sum of all point labels strictly decreases.

A generating family for a uniform set family is a collection $\mathcal{G}$ of sets of size at most $r$ such thatUse the following small-support generating lemma for extremal intersecting families, the auxiliary result permitted here. If $n>2r-t$, $j\ge 0$, andthen every maximum-cardinality left-compressed set family that is t-intersecting has a generating family contained in $\mathcal{P}([t+2j])$. Reflection gives the corresponding right-end supporting interval for a right-compressed optimum. The inequality is strict.

The main ideas of the generating lemma are as follows. When $n=2r-t+1$, its hypothesis forces $t+2j\ge n$, making the support conclusion automatic. Otherwise $n\ge 2r-t+2$. Choose inclusion-minimal compressed generators minimizing their furthest point $q$. Partition generators containing $q$ by size. A pair whose intersection would fall below $t$ on deleting $q$ must fill $[q]$ and have sizes summing to $q+t$. Compare the two replacements associated to those complementary size classes; counting their rank-$r$ extensions makes one replacement larger unless the sizes are equal. In that balanced case, put $q=t+2j+\delta$, where $\delta \ge 2$ is even. Delete $q$ from generators avoiding a suitably chosen earlier point. Averaging supplies a proportion at least $(q-t)/(2(q-1))$. The ratio of the guaranteed gain to the loss isIt exceeds one precisely when $n>(r-t+1)(2+(t-1)/(j+\delta /2))$, implied by the stated hypothesis. This contradicts maximal cardinality; redundant generators are removed after each replacement. These extension counts explain both the support bound and its strict threshold.

We also need the compatibility bound for complementary generating families, which has a short direct proof. Write $\overline{\mathcal{F}}=\{[n]\setminus A:A\in \mathcal{F}\}$. If $G$ generates $\mathcal{F}$ and $H$ generates $\overline{\mathcal{F}}$, thenOtherwise contain their union in a set $T$ of size $n-r+t-1$. Under $n>2r-t$ this size is at least both $r$ and $n-r$. Extend $G,H$ inside $T$ to sets $A,B$ of those respective sizes. Then $A,B^c\in \mathcal{F}$, whereas $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

The easy parameter ranges can now be disposed of. If $n\le 2r-t$, every two $r$-sets intersect in at least $t$ points, and $M(n,r,t)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. This is a candidate value too: choose $i=n-r$, for which the minimum possible intersection with $[t+2i]$ is exactly $t+i$. If $t=1$ and $n\ge 2r$, Question 1 gives $M(n,r,1)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=|{\mathcal{A}}_0|$. If $n=2r-t+1$, complementation of uniform intersecting families turns the problem into an intersecting family of rank $n-r=r-t+1$, on a ground set of size at least twice that rank. Question 1 then giveswith equality from that candidate, the family of all $r$-sets avoiding the last point.

It remains to treat $t>1$ and $n>2r-t+1$. Put $R=r-t+1$ andSince $N_R=2r-t+1$, there is $0\le k\le R-1$ with $N_{k+1}\le n<N_k$. Take a maximum left-compressed set family $\mathcal{F}$. Its complement family is right-compressed and has parametersIt is maximum for those parameters, since complementation is a cardinality-preserving bijection between the two intersection problems. Put $\ell =r-t-k=R-1-k$. The strict inequality $n<N_k$ impliesFor $k>0$, multiplying out reduces this to $nk<R(2k+t-1)$, exactly $n<N_k$; for $k=0$ it reduces to $t>1$. The reflected generating lemma therefore gives generators $\mathcal{H}$ for $\overline{\mathcal{F}}$ supported on

First suppose $N_{k+1}<n<N_k$. The original generating lemma supplies generators $\mathcal{G}$ supported on $X=[t+2k]$. If every $G\in \mathcal{G}$ has size at least $t+k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. The same conclusion follows if every $H\in \mathcal{H}$ has size at least $n-r-k$: every complement member then has at least that many points in $Y$, forcing each original member to have at least $t+k$ points in $X$. If neither condition holds, choose $|G|\le t+k-1$ and $|H|\le n-r-k-1$. Thencontradicting the proved compatibility bound. Thus $M(n,r,t)\le |{\mathcal{A}}_k|$, and the candidate itself attains equality.

Now suppose $n=N_{k+1}$. The earlier exceptional case excludes $k=R-1$. Since $t>1$, $n>N_{k+2}$, so the original generating lemma gives $\mathcal{G}$ supported on $[t+2k+2]$, while the same dual argument still gives $\mathcal{H}$ supported on $Y=[t+2k+1,n]$. If all $G$ have size at least $t+k+1$, then $\mathcal{F}\subseteq {\mathcal{A}}_{k+1}$. If all $H$ have size at least $n-r-k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. Otherwise a pair with $|G|\le t+k$ and $|H|\le n-r-k-1$ violates compatibility. HenceBoth candidates are available, so this proves the maximum formula also at the boundaries.

For completeness, their equality and the maximizing intervals follow from a direct count, with no appeal to the theorem. Moving from ${\mathcal{A}}_i$ to ${\mathcal{A}}_{i+1}$ adds sets containing both new coordinates and exactly $t+i-1$ old block points, and loses sets containing neither new coordinate and exactly $t+i$ old block points. ThusIn the nontrivial range, the gain-to-loss ratio is $\frac{(t+i)(r-t-i)}{(i+1)(n-r-i-1)}$. It exceeds, equals or falls below one according as $n$ is below, equal to or above $N_{i+1}$. Since the thresholds decrease with $i$ when $t>1$, the largest candidate is ${\mathcal{A}}_k$ in each strict interval and the consecutive candidates tie at $n=N_{k+1}$. This completes the proof of the cardinality theorem in every parameter range.

View a set family as a set of vertices of the Boolean lattice. The operation $D_i$ acts independently on each pair $\{S,S\cup \{i\}\}$, where $i\notin S$: it keeps a full or empty pair and moves a sole upper member down. Thus downward coordinate compression preserves cardinality.

Fix a tracing set $Y$. If $i\notin Y$, compression leaves the trace of a set family on $Y$ unchanged. If $i\in Y$, write $B_0,B_1\subseteq \mathcal{P}(Y\setminus \{i\})$ for the two sections of the old trace, according to absence or presence of $i$. The absent-$i$ section of the new trace is $B_0\cup B_1$. Its present-$i$ section is contained in $B_0\cap B_1$: an upper member survives only when its lower partner was also present in the original family. ConsequentlyIn particular, downward coordinate compression cannot create new set shattering.

Repeatedly apply any changing downward coordinate compression. Each change strictly decreases ${\sum }_{A\in \mathcal{F}}|A|$, so the process terminates at a down-set $\mathcal{D}$ with the same cardinality and with no larger trace on any $Y$. The Sauer-Shelah lemma says that a family shattering no $k$-element set satisfiesIndeed, the compressed down-set also shatters no $k$-element set. If it contained any member of size at least $k$, all subsets of a $k$-subset of that member would belong to the down-set, contradicting this restriction. Every member therefore has size at most $k-1$, giving the bound. Equivalently, VC dimension at most $d$ gives size at most ${\sum }_{j=0}^d\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The family of all sets of size at most $d$ attains this bound.

There is a different extremal example when $n\ge 3$. Toggle a fixed coordinate in the family of sets of size at most two:The symmetric difference is a bijection, so this family has $1+n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. On each tracing set $Y$, it simply toggles coordinate $1$ if $1\in Y$; thus it preserves trace cardinality and set shattering. A triple has seven trace patterns, not eight. The new family differs from the original one because it contains $\{1,2,3\}$. For $n\le 2$ the specified cardinality is $2^n$, so the entire power set is the unique family of that size; the different example requires $n\ge 3$.

For the final bound, let $e_i(\mathcal{F})$ count pairs $S,S\cup \{i\}$ both in the family. Deleting coordinate $i$ identifies precisely these pairs, soSuppose every deletion lost at least two members, so $e_i(\mathcal{F})\ge 2$ for every $i$. The trace inequality and preservation of cardinality show that $e_i(\mathcal{D})\ge e_i(\mathcal{F})$ after downward coordinate compression. The down-set $\mathcal{D}$ contains the empty set and every singleton. For each $i$, its second edge in direction $i$ has an upper endpoint of size at least two. Downward closure then supplies a pair $\{i,j\}\in \mathcal{D}$. The pairs in $\mathcal{D}$ therefore cover all $n$ coordinates, so at least $\lceil n/2\rceil$ pairs are needed. This proves two cube edges in every direction force many vertices:Taking the contrapositive gives the required answer:The threshold is sharp for every $n\ge 2$. Take the empty set, all singletons and $\lceil n/2\rceil$ pairs covering every coordinate. For even $n$, use the disjoint pairs $12,34,\dots ,(n-1)n$; for odd $n$, pair the first $n-1$ coordinates and add $(n-1)n$. This down-set has exactly $\lceil 3n/2\rceil +1$ members and at least two edges in every direction, so every $(n-1)$-coordinate trace has size at most $|\mathcal{F}|-2$. Adding further members preserves those pairs and therefore preserves the failure whenever a larger cardinality is feasible. For $n=1$, the putative counterexample cardinality is three, exceeding the size of the Boolean lattice; the sharpness construction naturally starts at $n=2$.

The Ehrenfeucht-Mostowski theorem asserts that an infinite first-order structure has, for any prescribed total order $I$, an elementary extension containing distinct order-indiscernibles $(c_i{)}_{i\in I}$. After a Skolem expansion, the Skolem hull of those generators is a model of the original complete theory. Every order automorphism of $I$ extends to a unique automorphism of this specified Skolem hull in the expanded language.

Choose a Skolem expansion $M^{\ast }$ of the original infinite structure: for each existential formula, select a witness function, including nullary functions when needed. Add constants $c_i$ for $i\in I$ and the elementary diagram of a structure of $M^{\ast }$, using separate names for its elements. Require $c_i\ne c_j$ for distinct indices, and for each formula $\phi$ in the Skolem language requirewhenever both index tuples are strictly increasing. These are the order-indiscernible sequence requirements.

Every finite fragment is satisfiable in $M^{\ast }$. Choose a countably infinite sequence of distinct elements of $M^{\ast }$. The fragment mentions only finitely many formulas and arities. Color increasing $k$-tuples of that sequence by the finite vector of truth values of its relevant $k$-ary formulas. The Ramsey theorem supplies an infinite homogeneous subsequence; repeat for the finitely many arities. Assign the finitely many named $c_i$ to distinct elements of the final homogeneous subsequence in increasing index order. The fixed finite part of the elementary diagram of a structure already holds in $M^{\ast }$. By the compactness theorem proved in Question 5, the full set of requirements has a model $N^{\ast }$, giving the required elementary extension and order-indiscernible sequence.

Let $H$ comprise all values of Skolem-language terms in finitely many $c_i$. It is closed under the witness functions. If $N^{\ast }\models \exists x\psi (x,\bar{h})$ for parameters in $H$, the specified witness function supplies a witness in $H$. Induction on formulas therefore gives $H⪯N^{\ast }$; its reduct is a model of $\mathrm{Th}(M)$. For infinite $I$, its cardinality is at most $\max (|I|,|L^{\ast }|,{\aleph }_0)$ and at least $|I|$.

For an order automorphism $\alpha :I\to I$, defineRewrite any finite list of indices in increasing order, allowing a term to repeat or omit variables. The order-indiscernible sequence property transfers every equality between terms and every relation among their values, making this definition well defined and elementary. Applying ${\alpha }^{-1}$ gives its inverse. All of $H$ is generated by the $c_i$ and the named Skolem functions, so an automorphism extending $\alpha$ must have precisely this action. Thus $\boxed{\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(H^{\ast })}$, with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a nonprincipal ultrafilter $U$ on $\kappa$ that is $\kappa$-complete: intersections of fewer than $\kappa$ members of $U$ remain in $U$. An elementary embedding $j:M\to N$ preserves truth of every first-order formula, with its parameters carried along by $j$.

The identity is always an elementary embedding of the universe into itself. The substantive question concerns a nonidentity embedding. In ZFC, the Kunen inconsistency theorem givesHere, as usual for class embeddings, restrictions to sets and the recursively defined critical sequence are available. We give the stationary-set proof, including its partition ingredient.

Suppose such a $j$ existed. It has a least moved ordinal $\kappa$, its critical point of an elementary embedding. To see why some ordinal must move, if all ordinals were fixed, induction on rank would fix every set: membership of $z$ in $j(x)$ is equivalent to membership of $z$ in $x$ once every lower-rank $z$ is fixed. A rank segment containing a moved set would then be fixed pointwise, a contradiction. The critical point is an uncountable cardinal. All finite ordinals and $\omega$ are definable and fixed. If $\kappa$ had cardinality $\mu <\kappa$, a bijection $f:\mu \to \kappa$ would be carried to a surjection $j(f):\mu \to j(\kappa )$ whose range still consists exactly of the fixed ordinals below $\kappa$, impossible since $j(\kappa )>\kappa$.

Put ${\kappa }_0=\kappa$, ${\kappa }_{n+1}=j({\kappa }_n)$ and $\lambda ={\sup }_{n<\omega }{\kappa }_n$. Applying $j$ to this Kunen critical sequence shifts it by one, so $j(\lambda )=\lambda$. Elementarity also gives $j({\lambda }^{+})={\lambda }^{+}$; write $\theta ={\lambda }^{+}$.

We need a stationary partition at a successor cardinal. If $S\subseteq {\lambda }^{+}$ is stationary, choose bijections $e_{\beta }:\lambda \to \beta$ for $\lambda \le \beta <{\lambda }^{+}$. For each $\xi <{\lambda }^{+}$, on the stationary tail $\{\beta \in S:\beta >\max (\lambda ,\xi )\}$ the function $\beta \mapsto e_{\beta }^{-1}(\xi )$ is regressive. The Fodor lemma supplies a stationary fiber $E_{\xi }$ with constant value $i_{\xi }<\lambda$. Some value $i$ occurs for ${\lambda }^{+}$ many $\xi$, since a union of $\lambda$ sets each of size at most $\lambda$ cannot have size ${\lambda }^{+}$. For distinct such $\xi$, their fibers are disjoint: $e_{\beta }(i)$ cannot equal two different ordinals. These fibers yield ${\lambda }^{+}$ disjoint stationary subsets; include any leftover points in one cell. Grouping cells also gives a partition into any nonzero number at most ${\lambda }^{+}$.

For completeness, the Fodor lemma used here follows from diagonal intersections of clubs. If a regressive function $f:S\to \theta$ had no stationary fiber, choose a club set $C_{\xi }$ disjoint from each fiber. The diagonal intersection $\{\beta <\theta :\forall \xi <\beta (\beta \in C_{\xi })\}$ is club by regularity and closure. A point $\beta$ in its intersection with $S$ would belong to $C_{f(\beta )}$, contradicting the choice of that club.

The set $S=\{\beta <\theta :\mathrm{cf}(\beta )=\omega \}$ is stationary: inside any club choose a strictly increasing countable sequence, whose supremum still lies below the regular uncountable $\theta$ and belongs to the club. Partition it as $⟨S_{\alpha }:\alpha <\kappa ⟩$. Its image $⟨T_{\alpha }:\alpha <j(\kappa )⟩$ is another stationary partition of the same $S$.

The set $C=\{\beta <\theta :j‘‘\beta \subseteq \beta \}$ is club. Closure is immediate. To get a member above any given ordinal, repeatedly bound the images of all earlier ordinals and take a countable supremum; regularity of $\theta$ keeps each bound below $\theta$. Choose $\beta \in C\cap T_{\kappa }$. Since $\mathrm{cf}(\beta )=\omega$, a countable cofinal sequence in $\beta$ and $j(\omega )=\omega$ give $j(\beta )=\beta$: the image sequence remains below $\beta$ by closure under $j$, and $j(\beta )\ge \beta$.

But $\beta \in S_{\alpha }$ for some $\alpha <\kappa$. Applying $j$ and using $j(\alpha )=\alpha$ gives $\beta =j(\beta )\in T_{\alpha }$, contradicting its membership in the disjoint cell $T_{\kappa }$. This proves the assertion. The use of axiom of choice in the cardinal and stationary-partition arguments matters; the conclusion here is explicitly in ZFC.

A Freiman 2-isomorphism is an injective map onto its image preserving pair-sum equality in both directions, with repeated summands allowed. Put $D=2A-2A$, so $D=-D$, $0\in D$, and $|D|<N$. We prove the half-size cyclic Freiman model with a sharp difference-set bound. Assume $A\ne \varnothing$; for an empty set the conclusion is immediate.

Choose an odd auxiliary prime $P>N$ large enough that reduction modulo $P$ is injective on $A$ and no nonzero element of $D$ reduces to zero. Choose a multiplier $t$ uniformly in ${\mathbb{Z}}_P^{\times }$. The forbidden residues areThey form a symmetric set, exclude zero since $P>N$, and have cardinality at most $2\lfloor (P-1)/N\rfloor$. For each nonzero $d\in D$, the product $td$ is uniform on the $P-1$ nonzero residues. Moreover, $td\in \mathcal{F}$ is the same event as $t(-d)\in \mathcal{F}$, so one need only sum over the $(|D|-1)/2$ opposite pairs. The union bound givesFix a multiplier avoiding all forbidden events. The use of opposite pairs is what achieves the threshold $N>|D|$ without an extra factor of two.

Represent each $ta(\mathrm{mod}P)$ by an integer $r(a)\in \{0,\dots ,P-1\}$. Partition these residues into the two half-intervalsAt least half of $A$ has representatives in one of them; call this subset $A^{\prime }$. Both intervals have diameter less than $P/2$, so for $a_1,a_2,a_3,a_4\in A^{\prime }$ the integersatisfies $|R|<P$.

Define $\varphi (a)=r(a)(\mathrm{mod}N)$. If $a_1+a_2=a_3+a_4$, then $R\equiv 0(\mathrm{mod}P)$, hence $R=0$ and the image relation holds. Conversely, if the image relation holds, then $R=jN$. If the original difference $d=a_1+a_2-a_3-a_4$ were nonzero, $R\equiv td(\mathrm{mod}P)$ would be nonzero; since $|R|<P$, this would be a forbidden residue in $\mathcal{F}$. Thus $d=0$.

Finally $\varphi$ is injective. If $\varphi (a)=\varphi (b)$, choose any $c\in A^{\prime }$ and apply the converse to $\varphi (a)+\varphi (c)=\varphi (b)+\varphi (c)$, obtaining $a+c=b+c$. ThereforeThe construction actually works for any integer $N>|D|$; the prime hypothesis in the question is sufficient.

Assume $X$ is nonempty, as is necessary for a probability measure to exist. Give its isometry group $I_X$ the uniform metricEvery distance-preserving self-map of a compact metric space is onto. Indeed, if $x_0\notin gX$, then $\delta =d(x_0,gX)>0$, and for $n>m$ the iterates satisfy $d(g^m{x}_0,g^n{x}_0)=d(x_0,g^{n-m}{x}_0)\ge \delta$. This infinite separated set contradicts compactness. Consequently $I_X$ is a group under composition, with the identity and inverses again isometries.

The metric $D$ is invariant under both left and right multiplication: left invariance uses preservation of distances, and right invariance uses surjectivity. Inversion is an isometry for $D$, and $D(gh,g^{\prime }{h}^{\prime })\le D(g,g^{\prime })+D(h,h^{\prime })$ proves continuity of multiplication. Moreover, $I_X$ is compact. A sequence of isometries has a subsequence converging at every point of a countable dense subset of $X$, by a diagonal argument. Their common Lipschitz constant $1$ and finite epsilon-nets of $X$ make this subsequence uniformly Cauchy. Its uniform limit preserves distances and is onto by the preceding argument. Thus $I_X$ is a compact metrizable topological group. A transitive group action means that for every $x,y\in X$ some $g\in I_X$ has $gx=y$.

We construct the invariant Borel probability measure directly. The Hall marriage theorem says that a finite bipartite graph with equal-sized vertex classes $A,B$ has a perfect matching precisely when every subset $S\subseteq A$ has at least $|S|$ neighbours in $B$. Its following consequence is useful. If $A,B$ are $\epsilon$-separated subsets of maximum cardinality in a compact metric space, join points whose distance is less than $\epsilon$. If some $S\subseteq A$ had fewer than $|S|$ neighbours, replacing those neighbours in $B$ by $S$ would produce a larger $\epsilon$-separated set. This contradicts maximal cardinality. Hence there is a bijection between $A$ and $B$ moving each point by less than $\epsilon$.

Choose ${\epsilon }_n\downarrow 0$ and maximum-cardinality ${\epsilon }_n$-separated sets $A_n\subset I_X$. Such sets exist: a finite covering by balls of radius less than ${\epsilon }_n/2$ bounds every separated set's cardinality. Fix $x_0\in X$ and define the empirical probability measuresFor $f\in C(X)$ let ${\omega }_f(r)={\sup }_{d(x,y)\le r}|f(x)-f(y)|$, which tends to zero with $r$ by uniform continuity. For every $h\in I_X$, left invariance of $D$ makes $h{A}_n$ another maximum-cardinality separated set. Match it to $A_n$ as above. ThenThe allowed compactness of probability measures on a compact metric space supplies a subsequence converging to $\mu$ in the weak-star topology. Passing to that limit for each fixed $h,f$ gives $\int fd\mu =\int f\circ hd\mu$. The same subsequence works for every $h,f$, since the displayed estimate held for all of them before taking the limit.

For uniqueness, put $F_n(x)=|A_n{|}^{-1}{\sum }_{a\in A_n}f(ax)$. For $x=h{x}_0$, right invariance of $D$ lets us match $A_{n}h$ with $A_n$. Transitivity therefore gives the uniform estimate $|F_n(x)-F_n(x_0)|\le {\omega }_f({\epsilon }_n)$ for every $x\in X$. If $\nu$ is any invariant Borel probability measure, thenTwo invariant probability measures consequently differ on the integral of $f$ by at most $2{\omega }_f({\epsilon }_n)$, hence agree on every continuous function. Continuous functions determine Borel probability measures on a compact metric space, so the invariant probability measure exists and is unique.

For a $d$-dimensional normed vector space, with unit ball $K$ and John ellipsoid $\mathcal{E}$, its volume ratio isIt is at least $1$ and invariant under invertible linear coordinate changes.

For ${\ell }_1^n$, the unit ball has volume $2^n/n!$: its intersection with each orthant is the standard simplex of volume $1/n!$. Its John ellipsoid is $n^{-1/2}{B}_2^n$. To verify maximum volume, let $A{B}_2^n$ be any centered inscribed ellipsoid. For each sign vector $\epsilon \in \{-1,1{\}}^n$, containment gives $|A^T\epsilon |\le 1$. Averaging over independent Rademacher random variables yields $\mathrm{tr}(A{A}^T)\le 1$. The arithmetic-geometric mean inequality for its squared singular values gives $|\det A|\le n^{-n/2}$. The scalar matrix $n^{-1/2}I$ attains this bound because $\Vert x{\Vert }_1\le \sqrt{n}|x|$. Centered ellipsoids suffice: if $a+A{B}_2^n$ is contained in the symmetric convex unit ball, averaging it with $-a+A{B}_2^n$ gives the centered copy with the same volume.

Using the stated Euclidean ball volume and $n=2k$,since $(2k)!/k!={\prod }_{j=k+1}^{2k}j\ge k^k$. Therefore $\mathrm{vr}({\ell }_1^{2k})\le \sqrt{8/\pi }$ uniformly in $k$.

The subsequent assertion for an arbitrary $2k$-dimensional space is false as printed. Here is a counterexample independent of any asymptotic section theorem. Take $E={\ell }_{\infty }^{2k}$. Its John ellipsoid is $B_2^{2k}$: an inscribed $A{B}_2^{2k}$ has every row of $A$ of Euclidean length at most $1$, so the Hadamard inequality gives $|\det A|\le 1$, attained by $A=I$. Let $F$ be any $k$-dimensional subspace and $f_1,\dots ,f_k$ an orthonormal basis of it. The random unit vectorhas $|x|=1$. Since ${\sum }_j{f}_j(i{)}^2\le 1$ for each coordinate $i$, the moment-generating function bound for independent Rademacher random variables givesChoose $r=\sqrt{2\log (8k)/k}$; the latter probability is at most $1/2$, so some unit vector in $F$ has $\Vert x{\Vert }_{\infty }\le r$. The proposed section inequality would therefore forceThus even one half-dimensional section cannot have the printed universal constant.

The valid orthogonal splitting with bounded volume ratio is that $L$ may depend on $V=\mathrm{vr}(E)$, and $L=32V^2$ suffices. This supplies a dimension-independent constant for the preceding ${\ell }_1^{2k}$ case, or whenever $V$ is bounded uniformly. We prove the complete qualified assertion, including its epsilon-net ingredient.

In John position, $\Vert x{\Vert }_E\le |x|$. Polar integration of the radial function $\rho (u)=1/\Vert u{\Vert }_E$ giveswhere $\sigma$ is normalized spherical measure.

A maximal $\epsilon$-separated subset of $S^{k-1}$ is an epsilon-net. Balls of radius $\epsilon /2$ about its points have disjoint interiors and lie in the ball of radius $1+\epsilon /2$. Comparing volumes bounds its cardinality by $(1+2/\epsilon {)}^k$. Finite existence follows from this packing bound, and maximality proves the net property without assuming a separate covering theorem.

Choose two orthogonal $k$-dimensional subspaces $F_0,F_0^{\perp }$ and one such net on each unit sphere. Rotate both by a common uniformly distributed orthogonal matrix $U$. This distribution can be obtained from Question 1 applied to the compact orthogonal group with its Frobenius metric; left and right multiplication are transitive isometries. Consequently $Uv$ is uniformly distributed on $S^{2k-1}$ for every fixed unit vector $v$. The union bound shows that the probability that some rotated net point has norm less than $2\epsilon$ is at mostSet $\epsilon =(32V^2{)}^{-1}$. Because $V\ge 1$, the bracket is at most $1/4+1/256$, and twice its $k$th power is less than $1$ for every $k\ge 1$. Some rotation therefore makes every point of both nets have norm at least $2\epsilon$.

The triangle inequality and $\Vert x{\Vert }_E\le |x|$ imply that $\Vert \cdot {\Vert }_E$ is $1$-Lipschitz for the Euclidean metric. Every unit vector of $U{F}_0$ or $U{F}_0^{\perp }$ is within $\epsilon$ of a good net point and thus has norm at least $\epsilon$. By homogeneity, on both orthogonal subspaces,For ${\ell }_1^{2k}$ the first computation gives the absolute choice $L=256/\pi$. The missing bounded-volume ratio restriction is essential; the literal unrestricted assertion cannot be proved.

Suppose $x^2\equiv -1(\mathrm{mod}p)$. Then $x\ne 0$ modulo the prime number $p$, so Fermat's little theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. But $p=4m+3$ makes $(p-1)/2=2m+1$ odd, and thereforeThis contradicts $1\not\equiv -1(\mathrm{mod}p)$, since $p$ is odd. Thus $-1$ is not a quadratic residue modulo $p$. Apply part (a) to the finite field $F={\mathbb{F}}_p$: the pairs $F^2$ with the given operations form a field, and there are $p$ choices for each coordinate, so its cardinality is $\boxed{p^2}$.

We first prove the needed Petridis minimal-growth lemma. For finite nonempty sets $A,D$, choose a nonempty $X\subseteq A$ minimizing $K_0=|X+D|/|X|$. Thus $|Y+D|\ge K_0|Y|$ for every $Y\subseteq X$, including the empty set. For any finite $T=\{t_1,\dots ,t_r\}$, defineThe sets $X_i+t_i$ partition $X+T$. If $x\notin X_i$, then $x+t_i\in X+t_j$ for some $j<i$, and therefore $x+D+t_i\subseteq X+D+t_j$. The newly contributed portion of $X+D+t_i$ consequently has size at mostSum over $i$ to obtain $|X+D+T|\le K_0|X+T|$. Apply this successively with $T=(r-1)D$ to get $|X+rD|\le K_0^r|X|$.

Use $D=-A$. The hypothesis implies $K_0\le |A-A|/|A|\le C$, so $|X-2A|\le C^2|X|$. We also prove the Ruzsa triangle inequality: for finite nonempty $U,V,W$,For each $s\in U-W$, fix $u_s,w_s$ with $s=u_s-w_s$. The map $(s,v)\mapsto (u_s-v,v-w_s)$ is injective: summing its coordinates recovers $s$, and then its first coordinate recovers $v$. This proves the inequality.

Apply it with $U=W=2A$ and $V=X$. Both right-hand factors have cardinality $|X-2A|$, givingThus $\boxed{K=C^4\text{ suffices}}$. This is the required case of the Plünnecke-Ruzsa inequality, proved here using the minimal-growth argument and the explicit injection. If $A$ is empty the conclusion holds directly.

We take $\alpha ,\beta >0$, as is necessary for the assertion. The nonvacuous cases have $0<\alpha \le 1/2$ and $0<\beta \le 1$. Put $n=|A|$ andWe prove a lower bound for $K$ by transferring small sumset growth through algebraic operations on the scalars. This gives a self-contained polynomial skew-sumset expansion over a prime field proof using the permitted Ruzsa triangle inequality, Ruzsa covering lemma and Plünnecke-Ruzsa inequality.

Since $|B|>1$, choose $b_0\in B\setminus \{0\}$. The bound $|b_{0}A+A|\le K|b_{0}A|$ and the mixed-set Plünnecke-Ruzsa inequality giveIn particular $|A+A|\le K^{2}n$ and $|3A-2A|\le K^{5}n$. Here repeated-set sums such as $3A$ allow independent choices from each copy.

For a scalar $t$, write $D(t)=|A+tA|/n$, and put $Q=A-A$ for the difference set. The Ruzsa covering lemma gives $tA\subseteq T_t+Q$ with $|T_t|\le D(t)$. Indeed choose a maximal family of disjoint translates $u+A$, with $u\in tA$; counting their union bounds the family size, and maximality forces every remaining translate to meet one of them.

For any $r,s$, the containments $A+(r+s)A\subseteq A+rA+sA$ and $A+rsA\subseteq r{T}_s+A+rQ$ give, after covering each copy of $rA,sA$,For the second bound, specifically $rQ=rA-rA\subseteq T_r-T_r+2Q$, and $A+2Q=3A-2A$. The Ruzsa triangle inequality also gives $|A-rA|\le |A+A||A+rA|/n$, so $D(-r)\le K^{2}D(r)$. These are the closure bounds for small skew-sumset scalars.

We next prove a growth lemma for the scalar sets. For $S\subseteq {\mathbb{F}}_p$ with $m=|S|\ge 2$, letIf $R\ne {\mathbb{F}}_p$, then $R+1$ is not contained in $R$: otherwise equal cardinality would make $R$ invariant under addition of one, which generates the entire prime field. Choose $r=1+(a-b)/(c-d)\notin R$. The map $(x,y)\mapsto x+ry$ on $S^2$ is injective. Indeed a collision with different second coordinates would express $r$ as a ratio of two differences from $S$, while equal second coordinates force equal first coordinates. Clearing the nonzero denominator puts its image insideso the latter set has at least $m^2$ elements. Here $SS$ is the product set, and $3SS-3SS$ denotes three independent product terms minus three others, not multiplication by the scalar three.