Combinatorics

A Steiner system $S(t,k,v)$ is a $v$-point set with $k$-point blocks such that every $t$-point subset is contained in exactly one block. Necessarily the number of blocks is $\left(\genfrac{}{}{0ex}{}{v}{t}\right)/\left(\genfrac{}{}{0ex}{}{k}{t}\right)$. This count is a necessary consistency check, not a substitute for proving exact containment. The small Witt design is $S(5,6,12)$.

The small Witt design is a Steiner system $S(5,6,12)$ with 132 blocks. A six-set duad-syntheme duality constructs it on two disjoint six-sets: two whole-half blocks, forty-five blocks of each of the types $(2,4)$ and $(4,2)$, and forty corresponding-partition blocks of type $(3,3)$. The internal-duad/cross-syntheme incidence rule proves that each five-set lies in exactly one of these blocks.

The complete graph on six points has fifteen edges and fifteen perfect matchings. Its six one-factorizations organize a dual incidence geometry exchanging points with factorizations and edges with matchings. The classical names are duads, synthemes and totals of synthemes. This geometry supports duad-syntheme duality on six points and a construction of the small Witt design.

A bijection from the points of one six-set to the totals of another extends by incidence to bijections from duads to synthemes, synthemes to duads, and totals to points. A duad maps to the intersection of its two point-totals. The same duality exchanges internal duads of a three-versus-three partition with cross synthemes of its corresponding partition. The latter rule follows by splitting the six cross perfect matchings into parity classes of three, yielding two triangles on the six totals.

A duad is an unordered pair of distinct points. On a six-point set there are $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ duads. They are the edges of the complete graph and are grouped into synthemes.

A syntheme partitions six points into three duads, equivalently a perfect matching of the complete graph. There are $6!/(2^{3}3!)=15$ synthemes. Every duad belongs to three. Two edge-disjoint synthemes extend to a unique total of synthemes: their union is a six-cycle, whose complement has a unique factorization into three matchings.

A total is a set of five edge-disjoint synthemes covering all fifteen duads of a six-point set. There are six totals; each syntheme belongs to two and every two totals share exactly one syntheme. Each total contains exactly one syntheme containing any prescribed duad. Totals are one-factorizations of the complete graph.

For an integer sequence with total sum one, exactly one cyclic starting position has every nonempty partial sum strictly positive. Starting after the last minimum of the proper partial sums proves existence. Two good starts would divide the sequence into two positive integer arc sums adding to one, proving uniqueness. This form counts cyclic prefix constraints in the cyclic Turán covering construction.

A cyclic digit run is a consecutive segment of a digit string whose successive digits all increase by one or all decrease by one modulo the base. For example, $8,9,0,1$ is an increasing decimal run. This refers to cyclic digit values, not to joining the final position of the string back to its first position. Overlapping run constraints can be counted with the inclusion-exclusion principle.

Finite geometry studies geometric incidence structures having finitely many points, such as finite projective and affine spaces.

An increasing subsequence of a sequence $x_1,\dots ,x_n$ is a sequence $x_{i_1}\le \cdots \le x_{i_m}$ selected at indices $i_1<\cdots <i_m$.

A longest increasing subsequence is an increasing subsequence of maximum length. Changing or deleting one term changes its length by at most one.

Additive combinatorics studies how the sizes and representation functions of sumsets reveal algebraic structure in subsets of abelian groups.

A frequency function built from an affine variable and its fractional part. Irrational $\gamma$ and $\beta$ can give many exact additive relations because each pair sum has only two possible floor carries. For example $\beta =\sqrt{3}$, $\gamma =\sqrt{2}$ gives $\gg N^3$ additive quadruples on $[-N,N]$, but agreement with every ordinary affine function occurs on only $o(N)$ shifts. Integer floor points underlying affine agreement must be collinear.

Use four parts indexed by $0,1,2,3$ in a cyclic group $G$, and include the triple missing part $i$ when $L_i\in A$. A transversal three-uniform tetrahedron then has the four values $S_1-i{S}_0$, where $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$, so it encodes a four-term arithmetic progression. Constant progressions give $|A||G{|}^2$ edge-disjoint tetrahedra. This is the bridge from the tetrahedron removal lemma to the Szemerédi theorem.

For every $\delta >0$, every sufficiently long integer interval has a nonconstant three-term arithmetic progression in each subset of subset density at least $\delta$. This is a theorem about additive combinatorics, distinct from the Roth theorem on approximation of algebraic irrational numbers. The Roth density-increment step proves it by repeatedly increasing subset density on a shorter arithmetic progression.

For fixed $\theta >0$, a sufficiently large finite set of integers with additive energy at least $\theta |A{|}^3$ has a nonconstant three-term arithmetic progression. The Balog-Szemerédi-Gowers theorem and Ruzsa modelling lemma reduce the problem to the Roth theorem on three-term arithmetic progressions in a dense cyclic model.

The product set of two sets of real numbers is $A\cdot B=\{ab:a\in A,b\in B\}$. It is a multiplicative counterpart of a sumset, not the Cartesian product $A\times B$.

For finite sets of nonzero real numbers, the multiplicative energy is the number of quadruples $(a,b,c,d)\in A\times B\times A\times B$ satisfying $a/b=c/d$. Swapping $b,d$ shows that it also counts quadruples with $ab=cd$. Thus $E(A,B)={\sum }_x{r}_{A\cdot B}(x{)}^2$, where $r_{A\cdot B}(x)$ counts product representations. The Cauchy-Schwarz inequality yields $E(A,B)\ge |A{|}^2|B{|}^2/|A\cdot B|$.

For finite sets of positive real numbers $A,B$ with $|B|\ge 2$, $E(A,B)\le 4\lceil \log |B|\rceil |A+A||B+B|$, with natural or binary logarithm. Partition ray occupancies of $A\times B$ into $\lceil \log |B|\rceil$ classes of multiplicative width $e$, or width $2$ for the binary convention. Injectivity of sums on two distinct rays and disjoint open planar sectors bound each class's sum of squared occupancies by $4|A+A||B+B|$. A singleton class contributes at most $|A||B|$. Combining this with the energy lower bound gives a sum-product inequality.

A corner consists of these three points in the integer grid, all contained in the set being studied. The displacement may be positive or negative, but must be nonzero, so the points are distinct. The corners theorem guarantees a corner in every subset of positive fixed density of a finite subset of a sufficiently large square grid.

For every $\delta >0$, all sufficiently large integers $n$ have the property that every $A\subseteq [n{]}^2$ with $|A|\ge \delta n^2$ contains a corner in an integer grid. The tripartite graph encoding of a grid turns the absence of a corner into a family of many edge-disjoint triangles but only quadratically many total triangles in a graph, contradicting the triangle removal lemma.

For a real-valued function $H$ on a nonempty finite Cartesian product $X\times Y$, its normalized cut norm is the maximum of $|{\mathbb{E}}_{x,y}H(x,y)1_A(x)1_B(y)|$ over $A\subseteq X,B\subseteq Y$. It measures all rectangular subset discrepancies. The convention using arbitrary test functions bounded by one is equivalent within a factor of four, by decomposing their positive and negative parts into indicator functions.

Non-abelian additive combinatorics studies product sets and configuration counts in noncommutative groups. Fourier analysis on a finite group and quasirandom groups connect small-dimensional group representations with multiplicative mixing.

For $f:G\to M_n(\mathbb{C})$ on a finite group, use uniform expectation over the solutions of $x{y}^{-1}z{w}^{-1}=e$ and the ordinary, unnormalized trace to define the displayed fourth-order quantity. If $T_{\rho }$ is its matrix Fourier block, this quantity equals ${\sum }_{\rho }{d}_{\rho }\mathrm{Tr}((T_{\rho }{T}_{\rho }^{\ast }{)}^2)$, so it is real and nonnegative. For a scalar function on an abelian group, it reduces to the usual fourth power of the Gowers uniformity norm of order two. The unnormalized trace means a unitary matrix-valued function can have fourth-order quantity as large as $n$.

If $\Vert f(x){\Vert }_{\mathrm{op}}\le 1$ and $\Vert f{\Vert }_{U^2}^4\ge cn>0$, select the singular values ${\lambda }_p\ge \sqrt{c/2}$ of the matrix Fourier blocks. Their weighted count $m={\sum }_p{d}_{{\rho }_p}$ lies between $cn/2$ and $2n/c$. Scaling unit right singular vectors and their corresponding unit left singular vectors by $\sqrt{d_{{\rho }_p}}$ gives matrices $U(p),V(p)$ satisfying ${\mathbb{E}}_{x}f(x)U(p){\rho }_p(x{)}^{\ast }={\lambda }_{p}V(p)$ and Hilbert-Schmidt inner product orthogonality within each chosen irreducible representation. The Schur averaging of rectangular matrices then gives ${\mathbb{E}}_x\Vert UP(x{)}^{\ast }b{\Vert }_2^2=\Vert b{\Vert }_2^2$ for the concatenated $U$ and the corresponding block diagonal matrix $P(x)$.

For $f:G\to M_n(\mathbb{C})$ and a degree-$d_{\rho }$ unitary irreducible representation, the matrix Fourier block is the operator $T_{\rho }$ on $M_{n\times d_{\rho }}(\mathbb{C})$ defined in the title. Its singular values ${\lambda }_{\rho ,j}$ satisfyPointwise operator norm at most one implies $\Vert T_{\rho }{\Vert }_{\mathrm{op}}\le 1$. These blocks are operators on a matrix space, rather than simply the entrywise scalar Fourier transform on a finite group without any reshaping.

A finite group is $m$-quasirandom if every nontrivial irreducible representation over the complex numbers has degree at least $m$. The trivial representation is excluded. Large $m$ suppresses correlations of products of arbitrary subsets, through product mixing in a quasirandom group.

For an $m$-quasirandom group, uniform expectations, and the normalized convolution on a finite group, a scalar mean-zero function $f$ satisfiesThe Fourier analysis on a finite group proof bounds each nontrivial matrix component of $f$ in operator norm using its weighted Hilbert-Schmidt norm. For subsets of subset density values $a,b,c$, the error in their normalized product count is at most $\sqrt{a(1-a)b(1-b)c(1-c)/m}$. In particular $abc>1/m$ guarantees a solution of $xy=z$ in the three subsets.

For a finite group, choose one unitary irreducible representation $\rho$ of degree $d_{\rho }$ from each equivalence class. One consistent normalized Fourier transform on a finite group convention is $\hat{f}(\rho )={\mathbb{E}}_{x}f(x)\rho (x)$. The Schur orthogonality relations giveThe normalized convolution on a finite group satisfies $\widehat{f\ast g}(\rho )=\hat{f}(\rho )\hat{g}(\rho )$ in this convention. Using $\rho (x{)}^{\ast }$ in the transform instead reverses that product order for scalar functions with the same normalized convolution on a finite group convention. The Fourier transform on a finite group has matrix-valued components even when the original function is scalar-valued.

For a scalar function on a group, use $(R_{a}f)(x)=f(xa)$ as the right-translation convention. For Fourier analysis on a finite group this gives $\widehat{R_{a}f}(\rho )=\hat{f}(\rho )\rho (a{)}^{\ast }$. Specifying whether $a$ or $a^{-1}$ appears in the definition avoids sign and multiplication-order ambiguity.

For a scalar function on a group, left translation by $a$ is $(L_{a}f)(x)=f(a^{-1}x)$. With the positive-representation convention for Fourier analysis on a finite group, $\widehat{L_{a}f}(\rho )=\rho (a)\hat{f}(\rho )$.

For a scalar function on a finite group, one normalized transform convention assigns the matrix ${\mathbb{E}}_{x}f(x)\rho (x)$ to each chosen unitary irreducible representation. This map is a weighted Hilbert space isomorphism by the Parseval identity on a finite group. Another common convention uses $\rho (x{)}^{\ast }$; the corresponding convolution theorem on a finite group then reverses the matrix product order for $(f\ast g)(x)={\mathbb{E}}_{y}f(y)g(y^{-1}x)$.

For the Fourier transform on a finite group, the displayed identity uses uniform expectation in the original function space and a weighted Hilbert-Schmidt inner product in the matrix components. In particular $\Vert f{\Vert }_2^2={\sum }_{\rho }{d}_{\rho }\Vert \hat{f}(\rho ){\Vert }_{\mathrm{HS}}^2$. For an abelian group, all $d_{\rho }=1$, and the identity becomes a sum of squared scalar coefficients.

The Fourier transform on a finite group convention $\hat{f}(\rho )={\mathbb{E}}_{x}f(x)\rho (x)$ has the displayed inversion formula. The sum is over one representative from each equivalence class of unitary irreducible representations. It follows from the Schur orthogonality relations and the regular representation decomposition, and holds at every group element without a limiting argument.

For scalar functions on a finite group, normalized convolution on a finite group is $(f\ast g)(x)=|G{|}^{-1}{\sum }_{y}f(y)g(y^{-1}x)$. It is associative and need not commute. Its identity is $|G|1_{\{e\}}$, rather than the unscaled indicator function of the identity element. The Fourier analysis on a finite group convention $\hat{f}(\rho )=\mathbb{E}f(x)\rho (x)$ turns it into matrix multiplication in the same order.

The normalized convolution on a finite group and the Fourier transform on a finite group convention with $\rho (x)$ satisfy the displayed identity. Substitute $x=yz$ in the defining expectation and use $\rho (yz)=\rho (y)\rho (z)$. With the convention using $\rho (x{)}^{\ast }$ instead, the scalar convolution has transform $\hat{g}(\rho )\hat{f}(\rho )$; multiplication order matters for noncommutative groups.

For nonempty finite sets $X,Y$ and a real-valued function $f$ on their Cartesian product, using uniform expectations, defineThis equals ${\mathbb{E}}_{y,y^{\prime }}({\mathbb{E}}_{x}f(x,y)f(x,y^{\prime }){)}^2$. Hence it is nonnegative, and vanishing forces $f=0$ by taking $y=y^{\prime }$. Absolute homogeneity and the box Cauchy-Schwarz inequality establish that it is a norm. This formula concerns real-valued functions; complex functions require appropriate complex conjugates in the definition.

For a complex function on $X_1\times X_2\times X_3$, its eighth power is the average of the conjugated product over the eight vertices of a coordinate cube. Three successive applications of the Cauchy-Schwarz inequality show that it bounds correlation with a product of three bounded functions, each omitting one coordinate. This is the analytic estimate behind the tetrahedron counting lemma.