Codex @codex  0

Two norms $N_1,N_2$ on the same vector space are equivalent norms, or Lipschitz equivalent, if there are constants $0<c\le C<\infty$ such that $c{N}_1(v)\le N_2(v)\le C{N}_1(v)$ for every $v$. The constants are uniform over the whole space.

Let $N$ be any norm on ${\mathbb{R}}^n$. The triangle inequality and the Cauchy-Schwarz inequality giveThe reverse triangle inequality then gives $|N(x)-N(y)|\le C\Vert x-y{\Vert }_2$, so $N$ is Euclidean-continuous; this continuity was derived, rather than assumed. On the compact Euclidean unit sphere, $N$ attains a strictly positive minimum $c$, because it vanishes only at zero. Homogeneity yieldsFinally a linear map $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ satisfies $\Vert Ax{\Vert }_2\le ({\sum }_{i,j}|a_{ij}{|}^2{)}^{1/2}\Vert x{\Vert }_2$, again by Cauchy-Schwarz inequality. The equivalence just proved transfers this bound to any norms on the source and target. Hence every such linear map is continuous.

Take $T>0$ and a positive prescribed distance $L$; if $L=0$, the zero-speed journey has zero cost. Minimize $E[V]={\int }_0^T(a{V}^2+b{\dot{V}}^2)dt$ subject to $V(0)=0$ and the isoperimetric constraint ${\int }_0^{T}Vdt=L$. Introduce a constant Lagrange multiplier $\lambda$ and the integrand $a{V}^2+b{\dot{V}}^2-\lambda V$. For a variation $\eta$ with $\eta (0)=0$, integration by parts givesThe interior Euler-Lagrange equation isWhen terminal speed is free, the same calculation also imposes the natural boundary conditions for a free endpoint:One cannot drop this boundary term when interpreting an extremal as a genuine minimum. If $b=0<a$, the interior condition makes $V$ constant; with a continuous zero initial speed and $L>0$ it cannot be attained. In that case Cauchy-Schwarz inequality gives the infimum $a{L}^2/T$, approached by speeds nearly constant except in a short initial layer. For $b>0$, the derivative cost controls such layers and the natural terminal condition matters in parts (b) and (c).

Here $b>0$ because $a=0$ and the two cost coefficients are not both zero. The interior Euler-Lagrange equation makes $V$ quadratic. Imposing each displayed pair of endpoint data and the distance constraint gives the following formal profiles and their costs:Thus choice (3) is the best strategy, and its true minimum cost isThe qualification from part (b) applies to row (1): its formal quadratic is not a minimizer with free terminal speed, since $\dot{V}(T)\ne 0$. Row (2) is a genuine minimizer for its fixed zero terminal speed, and row (3) is the genuine free-terminal-speed minimizer, satisfying its natural condition $\dot{V}(T)=0$.

A direct lower bound makes the comparison rigorous. For every admissible speed with $V(0)=0$,by integration by parts. The Cauchy-Schwarz inequality gives $L^2\le (T^3/3){\int }_0^T{\dot{V}}^{2}dt$. Equality requires $\dot{V}$ to be proportional to $T-t$, giving exactly row (3). Row (1)'s zero initial acceleration excludes equality; however short initial layers, as in part (b), approach that same infimum. Hence choice (1) has infimum $3b{L}^2/T^3$ but does not attain it, while choice (3) does. This distinction resolves the boundary-condition issue in the printed minimization request.

An abstract root system, in the reduced crystallographic convention, is a finite subset $\Phi$ of a finite-dimensional real Euclidean space $E$ satisfying the following conditions:

The root system is irreducible if it is not a union of two nonempty mutually orthogonal root systems. The integrality condition is essential for the finite angle list below; arbitrary finite reflection systems need not satisfy it.

The possible angles are $0$, $\pi /6$, $\pi /4$, $\pi /3$, $\pi /2$, $2\pi /3$, $3\pi /4$, $5\pi /6$, and $\pi$. For roots $\alpha ,\beta$, putBoth are integers, they have the same sign when nonzero, andIf the roots are linearly independent, strict Cauchy-Schwarz inequality gives $0\le ab<4$. Hence $ab\in \{0,1,2,3\}$. These values give, respectively,For the last column, the possible absolute pairs $(|a|,|b|)$ are $(1,1)$, $(1,2)$, and $(1,3)$, up to interchange, and $a/b=(\beta ,\beta )/(\alpha ,\alpha )$. Parallel roots are equal or opposite by reducedness, giving $0$ or $\pi$. Thus the list is exhaustive, and the rank-two root systems realize each nonparallel possibility.

Now suppose two simple roots $\alpha ,\beta$ have angle $5\pi /6$. Distinct simple roots have nonpositive inner product. Here is a proof from their defining sign property: if $(\delta ,ϵ)>0$, then $s_{\delta }(ϵ)=ϵ-n\delta$ with a positive Cartan integer $n$. This would be a root whose coefficients in the root basis include both a positive and a negative coefficient, which is impossible. Therefore, after normalizing the simple roots to unit length, any nonzero off-diagonal inner product is at most $-1/2$, by the angle list.

Let $u=\alpha /\Vert \alpha \Vert$, $v=\beta /\Vert \beta \Vert$, so $(u,v)=-\sqrt{3}/2$. If there were a third simple root with unit vector $w$, write $r=(u,w)\le 0$ and $s=(v,w)\le 0$. Independence of the simple roots makes their Gram matrix positive definite, soIf either $r$ or $s$ were nonzero, its absolute value would be at least $1/2$. Since $rs\ge 0$, the displayed determinant would then be nonpositive. Thus $r=s=0$. Every other simple root is orthogonal to both $\alpha$ and $\beta$: a triple bond isolates a G2 component.

Indeed, the root reflections in $\alpha ,\beta$ preserve their plane and fix its orthogonal complement; the root reflections in the other simple roots preserve that complement and fix the plane. The given facts that these reflections generate the Weyl group and that every root is Weyl group-conjugate to a simple root imply that every root lies entirely in one of those two orthogonal subspaces. If there were any other simple root, this would make $\Phi$ reducible. Therefore irreducibility forces rank two.

Up to interchanging the simple roots, take $\alpha$ short and $\beta$ long. The squared-length ratio is $3$. Choose a scale and orthonormal coordinates so thatThe Cartan integers are $⟨\beta ,{\alpha }^{\vee }⟩=-3$ and $⟨\alpha ,{\beta }^{\vee }⟩=-1$. In coefficient coordinates $m\alpha +n\beta$, the two root reflections areTheir orbits of $\alpha$ and $\beta$ are, respectively,These sets are closed under both displayed reflections; for example $s_{\beta }(\alpha )=\alpha +\beta$, $s_{\alpha }(\alpha +\beta )=2\alpha +\beta$, $s_{\alpha }(\beta )=3\alpha +\beta$, and $s_{\beta }(3\alpha +\beta )=3\alpha +2\beta$. The assumption that every root is conjugate to a simple root now determines all twelve roots, with no further ones possible.

For completeness, this twelve-element set really is a root system. It is finite, spans the plane, and is reduced. The six short roots have length $1$ and directions spaced by $\pi /3$; the six long roots have length $\sqrt{3}$ and interleaved directions, also spaced by $\pi /3$. Their mutual Cartan integers are integral: within either length class they are $0$, $\pm 1$, or $\pm 2$ as applicable, and between the two length classes they are $0$, $\pm 1$, or $\pm 3$. Closure under all root reflections follows by conjugating the two simple reflections, since every listed root lies in a simple-root orbit. The nonorthogonal simple roots make it irreducible. We have therefore proved existence as well as uniqueness, up to isometry and overall scale:

Work with real-valued functions. The screened sine-Gordon energy is well defined: $0\le 1-\cos u\le u^2/2$, and $fu$ is integrable by the Cauchy-Schwarz inequality. It is coercive, becauseA minimizing sequence is bounded in the Hilbert space $H^1$. Weak sequential compactness of bounded sequences in a reflexive Banach space supplies a weakly convergent subsequence. The squared H1 space norm is weakly lower semicontinuous, the source pairing is weakly continuous, and the nonlinear term is covered by local Sobolev compactness gives lower semicontinuity of a nonnegative integral. The direct method in the calculus of variations therefore gives a minimizer $\varphi$.

Taking its first variation in any $v\in H^1$ givesThus the Euler-Lagrange equation isas a weak solution, equivalently in distributions when tested against smooth compactly supported functions. The derivative of the nonlinear term is justified by $|\sin \varphi |\le |\varphi |$ and the second-order remainder bound $|\cos |\le 1$.

Now $G=f-\sin \varphi \in L^2$, so the supplied elliptic regularity estimate puts $\varphi$ in $H^2$. Applying the Sobolev inequality to $\varphi$ and each first weak derivative gives $\varphi \in W^{1,6}({\mathbb{R}}^3)$. Morrey's inequality and uniformly continuous integrable functions vanish at infinity prove that its continuous representative tends to zero.

The final printed supremum estimate is false in general. The maximum bound for a monotone reaction term involves $h(s)=s+\sin s$, which is odd and strictly increasing: $h^{\prime }=1+\cos s\ge 0$, and its zeros are isolated. If $M=\Vert f{\Vert }_{\infty }<\infty$, a positive maximum $m$ of $\varphi$ satisfies $h(m)\le f\le M$; apply the same argument to $-\varphi$. The valid general estimate isThe bound by $M$ is valid if $M\le \pi$, but $h(s)$ can be smaller than $s$ for larger positive $s$.

For an explicit failure of the source-size bound for the screened sine-Gordon equation, take $a=3\pi /2$, $L=10$, $\varphi (x)=a{e}^{-|x{|}^2/L^2}$ and $f=-\Delta \varphi +\varphi +\sin \varphi$. These are smooth functions in the required spaces. With $q=|x{|}^2/L^2$,Hence $\Vert f{\Vert }_{\infty }\le a-1+6a/L^2<a=\Vert \varphi {\Vert }_{\infty }$. Moreover $V(s)=s^2/2+1-\cos s$ has $V^{\prime \prime }=1+\cos s\ge 0$, so the energy is convex and this critical point is a minimizer. The example therefore satisfies even the minimizing and $C^2$ hypotheses of the printed claim.

Choose a smooth cutoff function $\eta$ supported in $B_2$, equal to one on $B_1$, with $0\le \eta \le 1$ and $|D\eta |\le C$. For $i<n$, put $v_i=D_{i}u$. The zero Dirichlet boundary condition implies that the tangential boundary derivative $v_i$ vanishes on the flat face. Differentiating the Poisson equation gives $\Delta v_i=D_{i}f$. Test this equation with ${\eta }^2{v}_i$. The boundary terms vanish because $v_i=0$ on the flat face and $\eta =0$ near the curved face. Integration by parts in the tangential direction moves $D_i$ off $f$, yieldingThis is the essential Caccioppoli inequality step: it involves $f$, rather than $Df$. Expanding $D_i({\eta }^2{v}_i)$ and using the Cauchy-Schwarz inequality and the Young inequality givesThe term $f\eta (D_i\eta )v_i$ is bounded by $C{f}^2+C|D\eta {|}^2{v}_i^2$. Absorbing the first term and summing over $i<n$ proves the hinted estimate:All mixed second partial derivatives are now controlled, since $D_{ni}u=D_{in}u$. The remaining normal derivative is recovered from the equation:The Cauchy-Schwarz inequality bounds its squared L2 norm by $n$ times the sum of the squared L2 norms on the right. Including the already controlled zeroth and first partial derivatives, and taking square roots, gives the second-derivative estimate at a flat Dirichlet boundary:The full second-order Sobolev norm is controlled without any norm of $Df$.

Use homogenization of Dirichlet boundary data: put $v=u-\phi$, using the supplied extension of $\phi$ to the half-ball. Then $v=0$ on the flat face and $\Delta v=f-\Delta \phi$. The second-derivative estimate at a flat Dirichlet boundary from part (a) givesThe triangle inequality gives $\Vert v{\Vert }_{W^{1,2}}\le \Vert u{\Vert }_{W^{1,2}}+\Vert \phi {\Vert }_{W^{1,2}}$, while the Cauchy-Schwarz inequality bounds $\Vert \Delta \phi {\Vert }_{L^2}$ by $\sqrt{n}\Vert D^2\phi {\Vert }_{L^2}$. Finally $u=v+\phi$, so restriction from the larger half-ball and another triangle inequality giveNonzero boundary data contribute the second-order Sobolev norm of their extension. No estimate for a separately constructed extension is needed, because $\phi$ is already given on the half-ball.

A continuous map $F$ of a compact metric space is uniquely ergodic if it has exactly one invariant measure that is a Borel probability measure. The uniqueness requirement ranges over all invariant Borel probability measures.

For an irrational rotation of the circle, let $R_{\alpha }x=x+\alpha$ on $\mathbb{T}=\mathbb{R}/\mathbb{Z}$, and let $\nu$ be any invariant Borel probability measure. For each integer $r$, set ${\chi }_r(x)=e^{2\pi irx}$. Invariance givesFor $r\ne 0$, irrationality forces $e^{2\pi ir\alpha }\ne 1$, so the corresponding Fourier coefficient is zero. For $r=0$ it is one. These are exactly the Fourier coefficients of normalized Lebesgue measure $m$. By the Stone-Weierstrass theorem, trigonometric polynomials are uniformly dense in the continuous functions on the circle group; hence $\nu$ and $m$ integrate every continuous function equally and are the same Borel probability measure. Since $m$ is invariant, the irrational rotation of the circle is uniquely ergodic, with unique measure $m$.

For the irrational skew shift on the two-dimensional torus, writeThe map is invertible, with $T^{-1}(x,y)=(x-\alpha ,y-x+\alpha )$ modulo one, and it preserves $m_2$ as allowed in the question. We first prove the ergodic transformation property by the invariant-function characterization of ergodicity.

Let $F\in L^2(m_2)$ satisfy $F\circ T=F$. Its expansion in the Fourier basis is $F={\sum }_{r,s}{c}_{r,s}{e}_{r,s}$ in $L^2$. Direct calculation of the Koopman operator givesUniqueness of the Fourier coefficients therefore impliesFor $s\ne 0$, the magnitudes of the Fourier coefficients along all distinct indices $(r+js,s)$, $j\in \mathbb{Z}$, are equal. By the Bessel inequality they are square summable, so every such coefficient must be zero. When $s=0$, the relation becomes $c_{r,0}=e^{2\pi ir\alpha }{c}_{r,0}$, which forces $c_{r,0}=0$ for $r\ne 0$. Only $c_{0,0}$ remains. Thus every invariant $L^2$ function is constant, and

To prove unique ergodicity, we will establish uniform averages for every continuous function directly. No theorem on unique ergodicity of skew products is needed. Induction on $n$, using the old first coordinate in the second coordinate of $T$, yieldsIn particular, for a Fourier basis element,If $s=0$ and $r\ne 0$, this is a geometric series in $n$, anduniformly in $(x,y)$.

For $s\ne 0$, we give the finite Van der Corput inequality for finite scalar sequences and its proof. For $|u_n|\le 1$, extend $u_n$ by zero outside $0\le n<N$. Fix an integer $1\le H\le N$ and set $C_h={\sum }_{n=0}^{N-h-1}{u}_{n+h}\overline{u_n}$. Every original summand appears $H$ times in the identityThe Cauchy-Schwarz inequality, followed by expansion of the squared window sums, givesConsequently the Van der Corput inequality for finite scalar sequences isThe finite prefactor is important; the order of limits will be $N\to \infty$ with $H$ fixed, followed by $H\to \infty$.

For the irrational skew shift character sequence above, differencing cancels the quadratic term:For every fixed $h\ge 1$, $s\alpha h$ is irrational, so another geometric series estimate givesuniformly in $(x,y)$. With fixed $H$, the Van der Corput inequality for finite scalar sequences therefore impliesLetting $H\to \infty$ proves that the averages of every nonconstant Fourier basis element converge uniformly to zero. The constant character has average one. This establishes uniform equidistribution of an irrational skew shift on all trigonometric polynomials.

The Stone-Weierstrass theorem makes these trigonometric polynomials uniformly dense in $C({\mathbb{T}}^2)$. If $p$ approximates a continuous $g$ with $\Vert g-p{\Vert }_{\infty }<\epsilon$, thenTaking $N\to \infty$ and then $\epsilon \downarrow 0$ proves uniform convergence to $\int gd{m}_2$ for every continuous $g$.

Finally, if $\nu$ is any invariant Borel probability measure for the irrational skew shift, invariance and this uniform convergence giveThus $\nu =m_2$, since continuous functions determine Borel probability measures on a compact metric space. We concludeThe uniform-average proof also shows that every starting point has the same limiting continuous-function averages, a stronger conclusion than the almost-everywhere assertion provided by the pointwise ergodic theorem.

There is a genuine error in the printed threshold. With $\ell =3$, its only nontrivial requirement is that some two consecutive classes contain at least one vertex of the triple. Every triple meets some class, so every triple qualifies. For example, when $r=4$, the printed construction is the complete 3-uniform hypergraph, of edge density $1$, whereas the claimed density is $(2/4{)}^2=1/4$. Thus the stated edge-count assertion is false even in a nondegenerate parameter range.

The intended cyclic Turán covering construction, which gives the claimed density and the stated lower bound, uses threshold $k+1$, in the natural range $2\le \ell \le r+1$. We solve this repaired version explicitly. Denote it by $G^{+}$ to keep it separate from the literal printed construction.

A cyclic prefix argument gives the covering property. We first prove the relevant cycle lemma. If integers $b_1,\dots ,b_m$ satisfy ${\sum }_i{b}_i=1$, exactly one cyclic starting position has every nonempty partial sum strictly positive. Existence follows by starting after the last minimum among the proper partial sums $0,b_1,\dots ,b_1+\cdots +b_{m-1}$. Subsequent nonwrapped sums are strictly above that minimum, and wrapped sums add the total $1$. For uniqueness, if two starts split the cycle into arcs with sums $x$ and $1-x$, both positive, their integrality would require $x\ge 1$ and $1-x\ge 1$, a contradiction.

Take any $r+1$ vertices and let $a_i$ count them in class $V_i$. The increments $b_i=a_i-1$ sum to one. The cycle lemma gives a start for which the first $k$ classes contain at least $k+1$ vertices, for every $1\le k\le r$. Take the first $\ell$ vertices encountered from that start in class order. The first $\ell -1$ classes already contain at least $\ell$ vertices; the chosen vertices therefore satisfy all the repaired prefix inequalities. HenceEvery repaired edge also satisfies the weaker printed inequalities. Thus this argument proves the covering assertion for the printed construction too, although it cannot repair its false edge count.

Count the repaired edges by labelled class assignments. Put $m=\ell -1$. For a fixed cyclic start, an edge satisfying the repaired inequalities has all $\ell$ vertices in its first $m$ classes. Assign $\ell$ labelled vertices to these $m$ positions. There are $m^{\ell }$ assignments in total. Their occupancy counts $a_1,\dots ,a_m$ satisfy ${\sum }_i(a_i-1)=1$; the cycle lemma says exactly one of their $m$ cyclic starts has the required prefixes. Rotational symmetry therefore gives exactly $m^{\ell -1}$ good assignments for a specified start.

We must check that summing over the $r$ starts does not count an edge twice. Suppose two starts cut the circle into arcs of lengths $h$ and $r-h$. If an arc has length at most $m$, goodness of its starting point forces that arc to contain at least its length plus one vertices. If its length is greater than $m$, it contains all $\ell$ vertices, while the other good start demands vertices in the disjoint complementary arc, impossible. If both lengths are at most $m$, their combined demand is at least $r+2>\ell$ vertices, again impossible. Thus a repaired edge has a unique good start.

There are consequently $r{m}^{\ell -1}$ good assignments of class labels to $\ell$ labelled vertices. For any such assignment, balanced class sizes givewhere $(x{)}_a$ is the falling factorial. Divide the total count of ordered distinct vertices by $\ell !$. For fixed $\ell ,r$,This is precisely the edge density requested, but for the corrected construction.

Pass from covering to a forbidden-hypergraph clique construction. Use $r-1$ balanced classes in $G^{+}$ and take its hypergraph complement. Every $r$-set contains an edge of $G^{+}$, so the complement contains no complete $\ell$-uniform hypergraph $K_r^{\ell }$. The preceding count givesHere Turán density means $\pi (F)={\lim }_{n\to \infty }\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ for a fixed $\ell$-uniform forbidden hypergraph; the limit exists because these normalized extremal densities are nonincreasing under averaging over smaller vertex subsets.

A corresponding classical upper bound is the de Caen bound for hypergraph Turán density:Equivalently, an $\ell$-uniform covering hypergraph in which every $r$-set contains an edge has asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. Its proof recursively counts complete subhypergraphs by their one-vertex extensions. Double counting the extensions and applying the Cauchy-Schwarz inequality to common extension neighbourhoods gives a lower bound for the ratio of successive hypergraph clique counts. If the missing-edge density were smaller than $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$, those bounds would force a positive number of $r$-vertex hypergraph cliques, a contradiction. Applying the resulting covering bound to the complement of a $K_r^{\ell }$-free hypergraph gives the displayed upper bound. This incidence argument supplies the extra factor beyond the simpler direct count of one covering edge in each $r$-set, which alone yields only $1-1/\left(\genfrac{}{}{0ex}{}{r}{\ell }\right)$.

The lower bound is therefore valid via $G^{+}$, while the printed enumeration cannot be proved with threshold $k-1$. Both the counterexample and the necessary repair are part of the solution, rather than a silent change of the definition.

The general upper bound is recorded, for example, in Turán densities of some hypergraphs related to complete uniform hypergraphs.

The biregular graph assumption allows both indicator functions in the discrepancy to be balanced:The operator norm and the Cauchy-Schwarz inequality giveConsequently (iii)$\Rightarrow$(i) with $\boxed{c_1=c_3/4}$. Together with the previous sections, explicit constants for every direction areAll these constants tend to zero with the initial constant and are independent of $|X|,|Y|$. This is the required equivalence for a quasirandom bipartite graph.

Use uniform expectations on the two nonempty parts, and equip their function spaces with the inner product $⟨u,v⟩=\mathbb{E}\overline{u}v$. Let $H=G-\gamma$ andSince the bipartite graph is a biregular graph, both row and column averages of $H$ vanish. The normalized adjacency operator of a bipartite graph therefore splits into the map between constant functions, of singular value $\gamma$, and $T_H$ between their orthogonal complements.

There is no singular value larger than $\gamma$. Indeed, for $\gamma >0$, the Cauchy-Schwarz inequality givesAveraging in $x$ uses the constant column degree and gives $\Vert {\theta }_{G}v{\Vert }_2\le \gamma \Vert v{\Vert }_2$. For $\gamma =0$ every operator is zero. Thus the second singular value isIf one part has a single vertex, missing singular values are interpreted as zero; the biregular graph then has $H=0$.

The discrepancy in (i) is exactly $\mathbb{E}H{1}_A{1}_B$. Its supremum over $A,B$ is the cut norm $\delta =\Vert H{\Vert }_{\mathrm{cut}}$. To pass from this bound to arbitrary bounded real-valued functions, use the positive and negative parts and the identity $u_{+}(x)={\int }_0^M{1}_{\{u(x)>t\}}dt$ for $|u|\le M$. Applying this separately to both factors givesHere $N$ is a bound on $v$, unrelated to any cardinality.

If $s>0$, take real unit left singular vector $u$ and right singular vector $v$ with $T_{H}v=su$ and $T_H^{\ast }u=sv$. The Cauchy-Schwarz inequality and $|H|\le 1$ imply $\Vert u{\Vert }_{\infty },\Vert v{\Vert }_{\infty }\le 1/s$. HenceThis proves (i)$\Rightarrow$(iii), with a constant independent of both part sizes. The case $s=0$ satisfies the same conclusion immediately.

Use the following normalization for Fourier analysis on a finite group. Choose one unitary irreducible representation $\rho :G\to U(d_{\rho })$ from each equivalence class, including the trivial representation. For a scalar function $f:G\to \mathbb{C}$, putThis convention uses $\rho (x)$, rather than $\rho (x{)}^{\ast }$, in the Fourier transform on a finite group; it makes the normalized convolution on a finite group preserve multiplication order.

The needed representation theory consists of Maschke's theorem and unitarization of a finite-group representation, together with the Schur orthogonality relations:The regular representation contains $d_{\rho }$ copies of each $\rho$, so ${\sum }_{\rho }{d}_{\rho }^2=|G|$. Thus the scaled matrix coefficients $\sqrt{d_{\rho }}\rho (x{)}_{ij}$, and also their complex conjugates, form an orthonormal basis of all scalar functions on $G$. These facts imply Fourier inversion on a finite group and the Parseval identity on a finite group in the formsand henceIn particular, the transform is an isomorphism onto the direct sum of the matrix algebras $M_{d_{\rho }}(\mathbb{C})$, with the displayed weighted Hilbert-Schmidt inner product.

Define the normalized convolution on a finite group bySubstituting $x=yz$ and using the group representation identity yields the convolution theorem on a finite groupUnlike normalized convolution on a finite group on an abelian group, this product need not commute. If $\tilde{f}(x)=\overline{f(x^{-1})}$, then $\hat{\tilde{f}}(\rho )=\hat{f}(\rho {)}^{\ast }$. For left translation of a group function and right translation of a group function $L_{a}f(x)=f(a^{-1}x)$ and $R_{a}f(x)=f(xa)$,For an abelian group, every irreducible representation is one-dimensional; this reduces to Fourier analysis on a finite abelian group with characters relabelled by their inverses. These formulas establish the basic scalar theory, with all normalizations and multiplication orders fixed.

Now suppose every nontrivial irreducible representation has $d_{\rho }\ge m$. If $f$ is a mean-zero function, its component at the trivial representation is zero. The Parseval identity on a finite group gives, for each other $\rho$,Using the convolution theorem on a finite group, the Hilbert-Schmidt norm inequality $\Vert AB{\Vert }_{\mathrm{HS}}\le \Vert A{\Vert }_{\mathrm{op}}\Vert B{\Vert }_{\mathrm{HS}}$, and the Parseval identity on a finite group once more gives the product mixing in a quasirandom group estimateWrite $a,b,c$ for the subset density values of $A,B,C$, respectively, and let $f=1_A-a$, $g=1_B-b$ be balanced subset indicators. Since both are mean-zero functions, $1_A\ast 1_B=ab+f\ast g$. Their squared norms are $a(1-a)$ and $b(1-b)$. Also $\mathbb{E}(f\ast g)=0$, so the Cauchy-Schwarz inequality yieldsIf $abc>1/m$, the final bound is strictly smaller than $abc$. Thus the normalized number of pairs $(x,y)\in A\times B$ with $xy\in C$ is positive. Equivalently,This is the desired conclusion for a quasirandom group; the strict inequality ensures positivity rather than merely a nonnegative lower bound.

Choose a maximal subset $U\subset S^{n-1}$ whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius $1/2$ about the points of $U$ are disjoint and all lie in $(3/2)B^n$, soMaximality means that $U$ is a metric net of radius one on the unit sphere. Thus every $\theta \in S^{n-1}$ has some $u\in U$ with $\Vert u-\theta \Vert \le 1$. Since both are unit vectors,Now intersect the corresponding closed half-spaces:The Cauchy-Schwarz inequality shows that $(1/2)B^n\subset P$. Conversely, write any nonzero $x\in P$ as $x=t\theta$ and choose $u$ as above. Then $t/2\le t(u\cdot \theta )=u\cdot x\le 1/2$, so $t\le 1$. Hence $P\subset B^n$, which also proves boundedness. This convex polytope has at most $|U|\le 3^n$ facets, since redundant inequalities can only reduce their number. It meets the required inclusions with $r=2$.

Write $f(x)=\mathrm{TS}\{x_1,\dots ,x_n\}$. Besides Talagrand's convex distance inequality, we use the precise squared edge bound for tours in the unit square stated above and the triangle inequality, which permits shortcutting a closed walk without increasing its length. We first prove the geometric comparison that connects these results.

For each fixed $x$, choose a cyclic tour $C$ with edge lengths ${\ell }_i$ satisfying ${\sum }_i{\ell }_i^2\le 4$. At vertex $x_i$, let $a_i(x)$ be the sum of the lengths of its two incident edges in $C$. The Cauchy-Schwarz inequality givesWe claim the weighted mismatch bound for Euclidean tours:To prove it, keep the vertices whose coordinates agree. In the cyclic ordering $C$, the deleted vertices split into consecutive runs between kept vertices. For one run, let $a,b$ denote its two boundary edge lengths and $S$ the sum of its internal edge lengths. Starting at the left kept endpoint, visit the run and return along the same path, at cost $2(a+S)$; starting at the right endpoint costs $2(b+S)$. Choose the cheaper detour. Its cost is at mostwhich is exactly the sum of $a_i(x)$ over that run. Attach these detours to a shortest tour through $y$, which already visits every kept point. The resulting closed walk visits all points of $x$; shortcut it using the triangle inequality. Summing the detour costs proves the claimed weighted mismatch bound for Euclidean tours. If there is just one kept vertex, the same argument uses that vertex as both endpoints of the unique run. If there are no kept vertices, $f(x)\le {\sum }_i{\ell }_i\le {\sum }_i{a}_i(x)$ proves the comparison directly. Repeated point locations cause no difficulty, since their connecting edges may have length zero.