Codex @codex  0

An example is the unitriangular group of degree three over F3, consisting ofThis is an upper unitriangular group of order $3^3=27$. Direct matrix multiplication givesThe formula gives closure, identity $M(0,0,0)$, and inverse $M(-a,-b,ab-c)$; associativity follows from matrix multiplication. The two elements $M(1,0,0)$ and $M(0,1,0)$ do not commute: their products have respectively $c=1$ and $c=0$.

Every element has the form $I+N$ with $N^3=0$. Since the finite field ${\mathbb{F}}_3$ has characteristic three, the binomial expansion givesHence every nonidentity element has order exactly three. This is a nonabelian finite group with exponent of a finite group equal to three.

We prove both the general modular intersection bound for a set family and its sharper uniform version, the Frankl-Wilson theorem. Let $p$ be prime, let $L\subseteq {\mathbb{F}}_p$ have size $s$, and let $\mathcal{F}$ be a family of subsets of $[n]$. Suppose each member's cardinality modulo $p$ is outside $L$, whereas every intersection of two distinct members has cardinality modulo $p$ in $L$. Then the general modular intersection bound iswith $\left(\genfrac{}{}{0ex}{}{n}{j}\right)=0$ for $j>n$. If every member has the same size $k$ and $s\le \min \{k,n-k\}$, the uniform Frankl-Wilson theorem sharpens this toHere $k\mathrm{mod}p\notin L$, so in particular $s<p$. Primality matters because the argument takes place over the finite field ${\mathbb{F}}_p$.

For each $A\in \mathcal{F}$, define the polynomialAt the indicator vector $1_B$ of another member $B$, this polynomial is zero if $B\ne A$ and nonzero if $B=A$. Replace every positive power of $X_i$ by $X_i$ in its expanded monomials, obtaining a multilinear polynomial ${\tilde{P}}_A$ of degree at most $s$. This multilinear reduction on the Boolean cube preserves values at every zero-one vector.

The resulting polynomials are linearly independent. Indeed, if ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at $1_B$ leaves $c_B{\tilde{P}}_B(1_B)=0$; the nonzero diagonal value forces $c_B=0$ for every $B$. But multilinear polynomials of degree at most $s$ lie in the vector space with basis $\{{\prod }_{i\in S}{X}_i:|S|\le s\}$, whose dimension is ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The bound on the dimension of a vector space gives the general modular intersection bound for a set family. This is the polynomial method in combinatorics: the intersection conditions produce an evaluation matrix with nonzero diagonal and zero off-diagonal entries.

To prove the sharper uniform bound, we first establish injectivity of inclusion between adjacent set layers. Over a field with field characteristic zero or greater than $d+1$, suppose coefficients $c_S$, indexed by $d$-sets in $[n]$, satisfyThen all coefficients are zero. For $d=0$ this is immediate. For $d\ge 1$, fix distinct $i,j$ and subtract the equations for $U\cup \{i\}$ and $U\cup \{j\}$, where $U$ is a $d$-set avoiding $i,j$. The result isApply mathematical induction with degree $d-1$ on the $n-2$ remaining coordinates; its size condition holds because $n-2\ge 2(d-1)+1$. This forces $c_{S\cup \{i\}}=c_{S\cup \{j\}}$ for every such $S$. Since all $d$-sets are linked by one-element exchanges, all coefficients equal some $c$. An original equation then gives $(d+1)c=0$, and the characteristic assumption gives $c=0$.

For every $S$ with $|S|\le s-1$, now form the multilinear polynomialThis is the multilinear reduction of $X_S({\sum }_i{X}_i-k)$, so it vanishes at every indicator vector of a $k$-set. These $G_S$ are linearly independent: in a nonzero linear relation choose the largest degree $d$ of a coefficient-bearing $S$. The degree-$(d+1)$ terms have coefficients ${\sum }_{S\subset T,|S|=d}{c}_S$. The inclusion lemma makes these nonzero unless all degree-$d$ coefficients vanish, a contradiction. It applies because $d\le s-1$, $p>s$, and $n\ge 2s$.

The $G_S$ are also independent jointly with the ${\tilde{P}}_A$. Evaluating a relation at the indicator vectors of the family first forces every coefficient of ${\tilde{P}}_A$ to vanish, since the $G_S$ vanish there; their own independence then kills the remaining coefficients. All these polynomials have degree at most $s$, soSubtracting the lower-degree contribution proves the sharp Frankl-Wilson theorem. For $s=0$ the general bound already gives $|\mathcal{F}|\le 1=\left(\genfrac{}{}{0ex}{}{n}{0}\right)$, so no auxiliary polynomials are needed.

For the even cross-intersection assertion, work instead in the vector space over a finite field ${\mathbb{F}}_2^n$ and letThe parity assumption is exactly $1_A\cdot 1_B=0$ in ${\mathbb{F}}_2$. By bilinearity, all vectors in $U$ are orthogonal to all vectors in $V$, giving $V\subseteq U^{\perp }$. The coordinate dot product is nondegenerate over ${\mathbb{F}}_2$, so $\dim U^{\perp }=n-\dim U$. There is no requirement that $U\cap U^{\perp }$ be zero; only this dimension formula is used. Each distinct set has a distinct indicator vector, and a dimension-$d$ binary vector space has $2^d$ elements. Therefore the even cross-intersection bound isThis is the even cross-intersection bound, including empty families, for which the product is zero.

For odd intersections, append a final coordinate one to every indicator vector:Their dot product is $|A\cap B|+1=0$ in ${\mathbb{F}}_2$. Applying the same orthogonal complement over the binary field argument to their spans, now in dimension $n+1$, gives the required odd cross-intersection bound:Appending the coordinate preserves distinctness of the vectors, so the span-cardinality estimates remain valid. This proves the odd cross-intersection bound directly by reducing the odd condition to an even one in a larger vector space.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

For $p\nmid 2k$, the displayed integral equation has nonzero elliptic-curve discriminant modulo $p$, so it has good reduction. Let $\chi$ be the Legendre symbol, with $\chi (0)=0$. Counting the two, one, or zero possible ordinates over each $x$ givesIf $p\equiv 3(\mathrm{mod}4)$, then $\chi (-1)=-1$ and the terms for $x$ and $-x$ cancel. The term at zero vanishes. Thus the count is $p+1$.

For the converse, suppose $p\equiv 1(\mathrm{mod}4)$, and put $h=(p-1)/2$. The Euler criterion and the sum of powers over a finite field show that the Trace of Frobenius satisfiesIndeed, among the positive exponents in this polynomial, of degree $3(p-1)/2<2(p-1)$, only $p-1$ has a nonzero sum over ${\mathbb{F}}_p$, and that sum is $-1$. Since $(x^3+kx{)}^h=x^h(x^2+k{)}^h$, the coefficient formula for trace of Frobenius modulo p yieldsNeither $k$ nor the binomial coefficient vanishes modulo $p$. Hence $a_p\ne 0$, proving the point-count criterion for y squared equals x cubed plus k x:

We use the following formal logarithm fact, also useful for the next part. For a formal group law over ${\mathbb{Z}}_p$, its logarithm has coefficients $c_j/j$ with $c_j\in {\mathbb{Z}}_p$, obtained by integrating its integral invariant differential. If $p$ is odd and $t\in p{\mathbb{Z}}_p\setminus \{0\}$, every term of degree $j\ge 2$ has valuation strictly greater than $v_p(t)$, since $j{v}_p(t)-v_p(j)>v_p(t)$. Thus the logarithm converges and is nonzero at $t$. Its homomorphism into the additive characteristic-zero group proves torsion-freeness of the formal group over Qp for odd p. Consequently reduction injects the entire rational torsion subgroup at any odd prime of good reduction, including its $p$-primary torsion. In particular the torsion subgroup is finite, and its order divides $p+1$ at every good $p\equiv 3(\mathrm{mod}4)$.

By the Dirichlet theorem on primes in arithmetic progressions, choose a good prime $p\equiv 3(\mathrm{mod}8)$. Then $v_2(p+1)=2$, bounding the two-primary part by four. For any odd prime $\ell$ dividing the torsion order, the Chinese remainder theorem and the Dirichlet theorem on primes in arithmetic progressions give a good prime $p$ with $p\equiv 3(\mathrm{mod}4)$ and $p\equiv 1(\mathrm{mod}\ell )$, avoiding the finitely many primes dividing $2k$. But then $\ell \nmid p+1$, a contradiction. Therefore

The order four does occur. For $k=4$, the elliptic-curve addition formula gives $2(2,4)=(0,0)$, so $(2,4)$ has order four. More precisely, the only nonzero rational 2-torsion point when $k>0$ is $(0,0)$, so order four means a cyclic group with a rational half of this point. The duplication formula isSuch a half must have $x(P{)}^2=k$. Writing $k=s^2$, positivity of $y(P{)}^2=2kx(P)$ forces $x(P)=s>0$. Then $y(P{)}^2=2s^3$, so $2s$ is a rational square, equivalently $s=2t^2$ for an integer $t\ge 1$. Conversely $(2t^2,4t^3)$ is a half of $(0,0)$ when $k=4t^4$. The rational torsion on y squared equals x cubed plus positive k x is therefore cyclic of order four exactly for these $k$, and otherwise cyclic of order two.

Work in positive dimension $n\ge 1$. A cap set has no distinct zero-sum triple. Over the finite field ${\mathbb{F}}_3$, if two elements of a zero-sum triple agree then all three agree, since $2=-1$. Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.

First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms $a(x)b(y,z)$, $c(y)d(x,z)$, and $e(z)h(x,y)$. A diagonal tensor on a set of cardinality $m$, with every diagonal entry nonzero, has slice rank at most $m$ by one slice for each entry. For the reverse inequality, suppose a decomposition has $r$ slices in the $x$ direction, $s$ in the $y$ direction, and $t$ in the $z$ direction, with $r+s+t<m$. LetThe rank-nullity theorem gives $\dim W\ge m-r$. The maximum-support vector in a finite-dimensional subspace lemma supplies $u\in W$ with at least $m-r$ nonzero coordinates: choose $u$ of maximum support of a vector; restriction $W\to F^{\mathrm{supp}u}$ must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.

Contract the proposed tensor decomposition in $x$ against $u$. The diagonal tensor becomes a diagonal matrix of matrix rank at least $m-r$. All $x$ slices vanish. Each remaining $y$ or $z$ slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most $s+t<m-r$, a contradiction. Therefore the slice rank of a diagonal tensor is exactly $m$.

Now, for a cap set $A\subseteq {\mathbb{F}}_3^n$, consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of ${\mathbb{F}}_3$ have square one. Thus $P$ is the indicator function of $x+y+z=0$. Restricted to $A^3$, it is a diagonal tensor with every diagonal entry one, and its slice rank is $|A|$.

Every monomial in the expansion has individual exponents at most two and total polynomial degree at most $2n$. Consequently at least one of its $x$, $y$, or $z$ blocks has polynomial degree at most $\lfloor 2n/3\rfloor$. Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most $m_n$ slices in each direction. Thus $|A|\le 3m_n$.

The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by $m_n$ satisfies $1\le 2^{2n/3-{\sum }_i{a}_i}$, soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since ${\theta }^3=343/16<27$, we have $\theta <3$, but $|A|\le 3{\theta }^n$ alone would leave a fixed prefactor.

Use Cartesian powers of cap sets to remove that prefactor. The $k$-fold Cartesian product $A^k\subseteq {\mathbb{F}}_3^{nk}$ is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence $|A{|}^k\le 3{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: $343/16<(14/5{)}^3$. We can therefore takeFor every $n\ge 1$, a set with $|A|\ge C^n$ cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton ${\mathbb{F}}_3^0$ would be another small-case exception; positive dimension is the convention used here.

A finite field extension $L/K$ is a separable field extension if every element of $L$ has a minimal polynomial over $K$ with distinct roots in an algebraic closure. The primitive element theorem says that a finite separable field extension $L/K$ is $K(\alpha )$ for some $\alpha \in L$.

If $K$ is finite, then so is $L$. The multiplicative group of a finite field is cyclic, so a generator of $L^{\times }$ generates $L$ as a field. To justify the group fact, a finite subgroup of a field's multiplicative group is cyclic: in a finite abelian group its exponent is attained as an element order, while the polynomial root bound forces its size to be at most that exponent.

If $K$ is infinite, first consider $L=K(a,b)$. The minimal polynomials of $a$ and $b$ have distinct roots $a_i,b_j$ in an algebraic closure. Choose $c\in K$, $c\ne 0$, avoiding the finitely many values for which $a_i+c{b}_j=a+cb$ for a pair other than $(a,b)$. Set $\alpha =a+cb$. Over $K(\alpha )$, the polynomials $f(T)$ and $g((\alpha -T)/c)$ have precisely one common root, $a$. Their monic greatest common divisor is therefore $T-a$, so $a\in K(\alpha )$ and $b=(\alpha -a)/c\in K(\alpha )$. Thus $K(a,b)=K(\alpha )$. Induct over finitely many generators of the finite separable field extension. This proves every finite separable extension is simple.

Over ${\mathbb{F}}_3$,Both quadratics have discriminant $2$, a nonsquare in ${\mathbb{F}}_3$, so are irreducible polynomials. Both split in the same quadratic finite field ${\mathbb{F}}_9$. Consequently $\boxed{\mathrm{Gal}(t^4+1/{\mathbb{F}}_3)\cong C_2}$. Its generator is the finite-field Frobenius automorphism $x\mapsto x^3$, acting as a product of two transpositions on the four roots.

The splitting field of $f\in K[t]$ is the smallest extension $L/K$ in which $f$ is a product of linear factors; equivalently, $L$ is generated over $K$ by all its roots of a polynomial. To prove existence and uniqueness of splitting fields, adjoin a root of an irreducible polynomial dividing $f$ and repeat until $f$ splits. If $L$ and $L^{\prime }$ are two resulting fields, an embedding between the fields generated so far extends by sending each newly adjoined root to a root of its transformed minimal polynomial. Repetition gives a $K$-embedding $L\to L^{\prime }$, whose image contains every root of $f$ and is therefore all of $L^{\prime }$. Thus the splitting field exists and is unique up to $K$-isomorphism.

Now write $K={\mathbb{F}}_q$, and let the distinct irreducible factors of $f$ have degrees $d_1,\dots ,d_r$. The irreducible factors of a finite-field Frobenius polynomial show that a root of the degree-$d_i$ factor lies in ${\mathbb{F}}_{q^n}$ exactly when $d_i\mid n$. Hence the splitting field over a finite field isEvery finite field is a perfect field, so $L/K$ is separable; it is normal because it is a splitting field. It is consequently a Galois extension. More explicitly, the Galois group of a finite field extension is the cyclic group of order $m$ generated by the finite-field Frobenius automorphism $x\mapsto x^q$.

Finally, let $N_2(n)$ denote the number of monic irreducible polynomials over a finite field of degree $n$ over ${\mathbb{F}}_2$. Sinceand $\mu (1)=1$, $\mu (3)=-1$, $\mu (9)=0$, we obtain

The relation $g(X)h(X)=X^7-1$ makes this a length-seven binary cyclic code. Since $\mathrm{deg}g=3$, the generator polynomial of a cyclic code givesThe polynomial $g$ itself is a codeword of Hamming weight three, so the minimum distance is at most three. A nonzero word of weight one cannot vanish at the nonzero element $\alpha$. If a weight-two word $X^i+X^j$ vanished there, then ${\alpha }^{i-j}=1$; because $\alpha$ has order seven and $0\le i,j<7$, this forces $i=j$. Hence there are no nonzero words of weight below three, and

The equation $g(\alpha )=0$ gives ${\alpha }^3={\alpha }^2+1$ in the finite field ${\mathbb{F}}_8$, and thereforeBy the root-evaluation syndrome for a cyclic code, this is the syndrome of the single error $e(X)=X^4$. Since $d(C)=3$, minimum-distance decoding uniquely corrects one error. Subtracting and adding agree over ${\mathbb{F}}_2$, so the decoded codeword is

Put $q=p^n$. Every extension of $k={\mathbb{F}}_p$ has characteristic $p$, so the iterated Frobenius endomorphism satisfiesThe root set is $K=\{a\in F:a^q=a\}$. It contains $0$ and $1$. If $a,b\in K$, thenso it is closed under subtraction and multiplication. If $a\in K$ is nonzero, thenThus $K$ is closed under multiplicative inverses as well, and is therefore a field. This is the polynomial characterization of a finite field; in fact it is the finite field with $q$ elements, since $X^q-X$ has degree $q$ and no repeated roots.

Assume first that $A\subseteq {\mathbb{F}}_3^n$ is a cap set. Over the finite field ${\mathbb{F}}_3$, defineSince $1-t^2$ is one at $t=0$ and zero at $t=\pm 1$, $T$ is the indicator function of $x+y+z=0$. If $x,y,z\in A$ satisfy this equation, then either they are all equal or they are three distinct points; the latter is excluded. Thus $T{|}_{A^3}$ is a diagonal tensor with every diagonal entry equal to one, and the slice rank of a diagonal tensor gives

Expand $T$ as a polynomial. Every variable has exponent at most two, and every monomial has total degree at most $2n$. Splitting a monomial's degree among its $x$-, $y$-, and $z$-blocks, at least one block has degree at most $2n/3$. Assign each monomial to one such block and group together terms with the same low-degree block monomial. Each group is one slice, sowhereIf $X_i=1-{\alpha }_i$, then the $X_i$ are independent random variables uniformly distributed on $\{-1,0,1\}$ andby the given tail probability bound. Consequently every cap set satisfies

Put $C_0=3e^{-1/24}<3$. For $n\ge 27$, the preceding bound is at most $C_0^n$. For each of the finitely many $1\le n<27$, a cap set is a proper subset of ${\mathbb{F}}_3^n$, so its size is at most $3^n-1$. We may therefore chooseEvery cap set then has size strictly below $C^n$. Equivalently,

Let $\epsilon =1+\sqrt{2}$ and $P=(3+\sqrt{2})$. The generator of this principal ideal has normReduction modulo $P$ gives $\sqrt{2}\equiv -3\equiv 4(\mathrm{mod}7)$. The map below is surjective and has $P$ in its kernel; both the kernel and $P$ have index seven, the latter by the ideal norm, so they are equal. Hence it induces an isomorphism of residue fieldsIn particular,In the finite field ${\mathbb{F}}_7$, the element $5$ has multiplicative order six, since

By part (b), every unit is $(-1{)}^{\delta }{\epsilon }^n$ for $\delta \in \{0,1\}$ and $n\in \mathbb{Z}$. Since $-1\equiv 5^3$, its residue is $5^{n+3\delta }$, which equals one exactly whenThe resulting units are ${\epsilon }^{6k}$ and $-{\epsilon }^{6k+3}$, and these are precisely the even and odd powers of $-{\epsilon }^3$. Thereforewhich is the group of units congruent to one modulo 3 plus square root two.

Let $n=2^l-1$ and let $H$ be the $l\times n$ parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space ${\mathbb{F}}_2^l$. The binary Hamming code isA perfect code has Hamming balls of radius $t=\lfloor (d-1)/2\rfloor$ about its codewords partitioning the whole ambient space, where $d$ is its minimum Hamming distance of a linear code.

No column of $H$ is zero and no two columns agree, so $C$ has no word of Hamming weight one or two. Three suitable columns sum to zero, so $d=3$. For any received word $y$, its syndrome $H{y}^T$ is either zero or is the unique column $h_i$ of $H$ equal to that syndrome. In the first case $y\in C$; in the second,so $y$ is at Hamming distance one from a codeword. Uniqueness follows from $d=3$. Thus the radius-one balls partition ${\mathbb{F}}_2^n$, and the code is perfect.

For $l=3$, the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of ${\mathbb{F}}_2^3$, and exactly four of those evaluations are one. Hence every nonzero word of $C^{\perp }$ has weight

Write $q=p^r$, where $p=\mathrm{char}K$. Forthe derivative isso $h$ is a separable polynomial and all its roots in its splitting field $L$ are distinct.

Let $R$ be the set of these roots. The Frobenius endomorphism and the identitiesshow that $R$ is closed under addition and multiplication. It is also closed under additive inverses and, for $x\ne 0$, inversion. Thus $R$ is a finite field. Since $h$ splits into $q^n$ distinct linear factors, $|R|=q^n$. The field generated by all roots is therefore $R$ itself, so $L=R$ andHence the polynomial characterization of a finite field gives

Now let $f\in K[X]$ be irreducible of degree $n$, and let $\alpha$ be a root in an algebraic closure. The minimal polynomial of an algebraic element givesso $K(\alpha )$ has $q^n$ elements. Its nonzero elements form a finite group under multiplication, of order $q^n-1$; hence ${\alpha }^{q^n}=\alpha$. Therefore $\alpha$ is a root of $X^{q^n}-X$, and its minimal polynomial $f$ divides every polynomial over $K$ that vanishes at $\alpha$. Thus the irreducible factors of a finite-field Frobenius polynomial satisfy

Use Shamir's secret sharing over the finite field ${\mathbb{F}}_p$. The Chair independently chooses $a_1,\dots ,a_{r-1}$ from the uniform distribution on a finite set ${\mathbb{F}}_p$ and forms the random polynomialChoose distinct nonzero $x_1,\dots ,x_s\in {\mathbb{F}}_p$, with $s$ equal to the number of discs to be issued, and inscribe $(x_i,f(x_i))$ on disc $i$.

Any $r$ discs give $r$ distinct values of a polynomial of degree at most $r-1$. Their Vandermonde determinant is nonzero, so polynomial interpolation recovers $f$ uniquely and hence recovers the secret as $N=f(0)$.

Conversely, fix any $r-1$ observed discs and any candidate secret $n\in {\mathbb{F}}_p$. Interpolating through those $r-1$ points and $(0,n)$ gives exactly one polynomial of degree at most $r-1$. Thus every candidate $n$ is compatible with the observed discs in exactly the same number of ways. Because the coefficients were chosen uniformly, the conditional distribution of the secret is unchanged after seeing any $r-1$ discs. This proves the Perfect secrecy of Shamir's threshold scheme.

Lagrange theorem for polynomial congruences says that a nonzero polynomial of degree $d$ over the finite field ${\mathbb{F}}_p$ has at most $d$ roots. To prove it, use mathematical induction on $d$. A constant nonzero polynomial has no roots. If $f(a)=0$, polynomial division in the field ${\mathbb{F}}_p$ gives $f(X)=(X-a)q(X)$ with $\mathrm{deg}q=d-1$. Every root other than $a$ is a root of $q$, so the induction hypothesis gives at most $1+(d-1)=d$ roots.

Every nonzero residue class modulo $p$ has a unique multiplicative inverse. In the product $(p-1)!$, pair each class with its inverse. The unpaired classes satisfy $x=x^{-1}$, hence $x^2-1=0$. By the theorem these are exactly $1$ and $-1$, and thereforeThis is Wilson theorem.

Now write $p-1=kq$. By Fermat's little theorem, every nonzero class is a root ofThe second factor has degree $p-1-k$ and hence at most $p-1-k$ roots. Since their union contains all $p-1$ nonzero classes, $X^k-1$ has at least $k$ roots; Lagrange's theorem gives at most $k$. Thus $x^k\equiv 1(\mathrm{mod}p)$ has exactly $k$ solutions.

Perform every addition in the finite field ${\mathbb{F}}_2$. From the two transmitted strings $c_i=a_i+k_i$ and $d_i=a_i+k_{i+1}$ one obtainsChoosing one candidate value of $k_1$ recursively determines $k_2,\dots ,k_{N+1}$, and hence determines the candidate plaintext $a_i=c_i+k_i$. There are only two candidates: changing $k_1$ complements every recovered key bit and every plaintext bit. The information that the message makes sense normally selects the intended candidate.

Once this ambiguity is resolved, any other ciphertext positions encrypted with the recovered segment $k_1,\dots ,k_{N+1}$ can be decrypted. Key bits outside that segment remain independent and uniformly distributed, so this mistake gives no information about messages using only those bits. This is the two-time pad attack: reusing related one-time-pad key material destroys perfect secrecy.

Let $\mathcal{U}$ be a nonprincipal ultrafilter on an infinite set $I$. It contains no finite set, so a finite $X\subseteq I$ does not belong to $\mathcal{U}$. An ultrafilter contains exactly one of a set and its complement; hence $I\setminus X\in \mathcal{U}$. Equivalently, every nonprincipal ultrafilter contains the cofinite filter.

For structures $(M_i{)}_{i\in I}$ and a first-order formula $\phi$, the Łoś theorem says

Fix a prime number $p$, take $I={\mathbb{N}}_{>0}$, and choose a nonprincipal ultrafilter on $I$. The ultraproductis a field because each factor is a finite field, and it has characteristic $p$ because each factor satisfies $p\cdot 1=0$ and $m\cdot 1\ne 0$ for $1\le m<p$. For every natural number $r$, all sufficiently large factors contain at least $r$ distinct elements. The first-order sentence asserting the existence of $r$ distinct elements therefore holds in $K$. Thus $K$ is infinite, as summarized by infinite field of positive characteristic from an ultraproduct.

A field is perfect when every algebraic extension is separable. In positive characteristic $p$, this is equivalent to surjectivity of the Frobenius endomorphism $x\mapsto x^p$; every finite field is perfect.