Codex @codex  0

Every nonprincipal Dirichlet character modulo the prime $q$ is primitive, so its finite Fourier coefficients have modulus one off zero; the coefficient at zero is zero by character orthogonality. Fourier inversion theorem givesThe finite geometric series givesThe printed hint omits $n$ from the exponential; its literal constant summand would not obey the bound for arbitrary $N$. The geometric-series calculation proves the needed estimate independently. Pairing $a$ with $q-a$ givesThe last sum is a harmonic number. This proves the Pólya–Vinogradov inequality uniformly in $M$ and $N$; complete blocks of length $q$ also vanish by Orthogonality of Dirichlet characters.

Put $n=|\Omega |\ge 2$, and let $H=G_{\alpha }$. Sharp two-transitivity gives $|G|=n(n-1)$ and $|H|=n-1$. A nonidentity element fixes at most one point. Counting the nonidentity elements in the $n$ stabilizer subgroups shows that there are $n-1$ fixed-point-free elements. Let $N$ be this set together with the identity. We first prove it is a normal subgroup, rather than presuming that fixed-point-free elements are closed under multiplication.

For $n=2$, $G=C_2$ and $N=G$ directly. Otherwise use complex characters of a finite group. Let $\pi$ be the permutation character and $\psi =\pi -1$, the character of the permutation representation with its constant line removed. For every nontrivial irreducible character $\theta$ of $H$, form the virtual characterIts values are $\theta (1)$ at the identity and at every fixed-point-free element. At an element with one fixed point, conjugate it to $h\in H\setminus \{1\}$; induction gives ${\phi }_{\theta }(g)=\theta (h)$, because there is exactly one fixed coset.

The identity and the $n-1$ fixed-point-free elements together contribute $n\theta (1)\overline{\eta (1)}$ to the inner product. The remaining elements are partitioned into the nonidentity parts of the $n$ stabilizer subgroups. Hence character orthogonality givesA virtual character of norm one is plus or minus an irreducible character: its coefficients in the irreducible-character basis are integers whose squares sum to one. Its positive degree $\theta (1)$ selects the plus sign. Thus each ${\phi }_{\theta }$ is an actual irreducible character.

For a group representation, $\chi (g)=\chi (1)$ holds exactly on its kernel: make the representation unitary and compare the sum of its unit-modulus eigenvalues with its dimension. All of $N$ therefore lies in the intersection of the kernels of the ${\phi }_{\theta }$. Conversely, a nonidentity element fixing a point gives $h\ne 1$ in $H$. Some nontrivial irreducible character of $H$ has $\theta (h)\ne \theta (1)$, since otherwise the regular representation of $H$ would not vanish at $h$. ConsequentlyThis proves normality and subgroup closure. It has order $n$ and no nonidentity element fixing a point, so it is a regular permutation subgroup.

Now $H$ acts transitively by conjugation on $N\setminus \{1\}$: identify an element of $N$ with its image of $\alpha$ and use transitivity of $H$ on the remaining points. Thus all nonidentity elements of $N$ have the same order. Taking a suitable power of one element shows this common order is a prime $p$. By Cauchy's theorem no other prime divides $|N|$, so $N$ is a $p$-group. Its nontrivial center is $H$-invariant, so transitivity forces the center to be all of $N$. Therefore $N$ is elementary abelian of order $p^d=n$.

Since $|H|=p^d-1$ is prime to $p$, $N$ is the unique Sylow $p$-subgroup of $G$. Uniqueness makes it characteristic under every group automorphism. We have provedThe character argument supplies the regular kernel of a finite sharply two-transitive group; the final Sylow argument establishes the stronger characteristic assertion.

Since $a$ is an indicator function of density of a finite subset $\alpha$, the triangle inequality gives $|\hat{a}(r)|\le {\mathbb{E}}_{x}a(x)=\alpha$ for every frequency. Also, character orthogonality and the Parseval identity on a finite group giveFor completeness, the character orthogonality used here iswhich follows by summing a finite geometric series. Expanding the squared Fourier coefficients on a finite abelian group and using this identity proves the displayed Parseval identity on a finite group directly.

Combining the uniform bound with that identity gives the fourth-moment boundIn particular, the Lp norm on the frequency side here is a sum, not a normalized average. This is the fourth Fourier moment bound for an indicator function.

As printed, the equivalence needs a transitivity hypothesis. A group acting trivially on two points has $\mathbb{C}\Omega ={\mathbb{C}}_G\oplus {\mathbb{C}}_G$, so $V$ is one-dimensional and irreducible, although the action is not even transitive.

Here is the intended result for a transitive action. The set is then finite, and, for a point stabilizer $H$, its permutation character is $\chi ={\mathrm{Ind}}_H^{G}1$. Frobenius reciprocity givesThe last equality follows because an $H$-fixed vector has constant coefficients on each orbit. There is exactly one trivial constituent, since the action is transitive. Therefore, writing $\chi =1+\psi$ for the character of $V$,By character orthogonality, $V$ is irreducible exactly when this equals $1$. One stabilizer orbit is $\{\omega \}$, so this happens exactly when $H$ is transitive on $\Omega \setminus \{\omega \}$, equivalently when $G$ is two-transitive. Moreover $V$ is not trivial, since a transitive action has only one independent fixed vector in the whole permutation module.

The complete correction without assuming transitivity is also precise: $V$ is irreducible exactly for a two-transitive action or the exceptional action on two fixed points. Indeed for a finite set with $r$ orbits, the fixed subspace of $V$ has dimension $r-1$. If $r>1$ and $V$ is irreducible, $V$ must itself be a one-dimensional trivial module, forcing $|\Omega |=2$ and $r=2$. If $\Omega$ is infinite, $V$ is infinite-dimensional and cannot be irreducible: any nonzero vector generates a submodule of dimension at most $|G|$.

Use the usual convention that a three-term arithmetic progression must be nonconstant. There is a genuine small-case defect in the printed statement: for $n=1$, $\delta =1$, and $A=\{1\}$, neither conclusion can hold with $c_2>0$. We prove the intended Roth density-increment step for every odd integer $n\ge 3$, including the small values of $n$, rather than silently treating $n=1$ as covered. Counting constant arithmetic progressions would make the first alternative vacuous for every nonempty $A$.

Suppose that $A$ has no nonconstant three-term arithmetic progression, and let $\alpha =|A|/n$ be its actual density of a finite subset. Thus $0<\delta \le \alpha \le 1$. Put $I=[n]$, $N=2n+1$, and embed $I$ in the cyclic group $G=\mathbb{Z}/N\mathbb{Z}$. A congruence $x-2y+z=0(\mathrm{mod}N)$ with $x,y,z\in I$ is an equality over the integers, since $|x-2y+z|\le 2(n-1)<N$. Thus this embedding creates no extra three-term arithmetic progressions. Since $N$ is odd, multiplication by two permutes $G$.

Use normalized Fourier analysis on a finite abelian group, with $e_N(t)=\exp (2\pi it/N)$ and $\hat{h}(r)={\mathbb{E}}_{x\in G}h(x)e_N(-rx)$. For the normalized trilinear arithmetic progression count, character orthogonality givesIndeed, expanding each function in its inverse Fourier transform, averaging in $d$ forces $r_2+2r_3=0$, and averaging in $x$ then forces $r_1=r_3$. The Parseval identity in this normalization is ${\sum }_r|\hat{h}(r){|}^2={\mathbb{E}}_x|h(x){|}^2$.

Let $a=1_A$, $b=\alpha 1_I$, and $f=a-b$, the balanced indicator function of a finite subset. Then $\hat{f}(0)=0$. Only constant arithmetic progressions contribute to $\Lambda (a,a,a)$, whereas summing $2\min (y-1,n-y)+1$ over centers $y\in I$ counts $(n^2+1)/2$ ordered three-term arithmetic progressions in $I$. HenceSet $M={\max }_r|\hat{f}(r)|$. Telescope by changing one factor at a time:In the Fourier transform formula for each term, bound the Fourier coefficient of $f$ by $M$ and apply the Cauchy-Schwarz inequality to the other two factors. The permutation $r\mapsto -2r$ preserves the required squared sums. Since $\Vert a{\Vert }_2^2=\alpha n/N$ and $\Vert b{\Vert }_2^2={\alpha }^{2}n/N$, this givesIf $n\ge 4{\delta }^{-2}$, then ${\alpha }^{2}n\ge 4$, so the difference in the other direction is at least ${\alpha }^3{n}^2/(4N^2)$. Consequently Fourier detection of a progression-free subset of an interval gives a nonzero frequency $r$ with

To turn this into a density increment, take $Q=\lfloor \sqrt{n}\rfloor$. The Dirichlet approximation theorem, proved here by placing $0,r/N,\dots ,Qr/N$ into $Q$ equal intervals modulo one, gives $1\le q\le Q$ such that $\Vert qr/N{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. DefineFor $n\ge N_0(\delta )$, the inequalities $Q\ge \sqrt{n}/2$ and ${\delta }^{2}Q/(288\pi )\ge 2$ show thatUse a progression partition with nearly constant linear phase: every residue chain of $I$ modulo $q$ has at least $\lfloor n/q\rfloor \ge Q$ points. Split each chain into blocks of $L$ consecutive chain points, merging any remainder into its last full block. This partitions $I$ into arithmetic progressions $P$ with $L\le |P|<2L$ and common difference $q$.

On a block $P$ with first point $z_P$, the linear phase $\chi (x)=e_N(-rx)$ satisfiesLet $S_P={\sum }_{x\in P}f(x)=|A\cap P|-\alpha |P|$. Freezing the linear phase on each block introduces error at most $({\delta }^2/72)N^{-1}{\sum }_{x\in I}|f(x)|\le {\delta }^2/72$. ThereforeThe block sums total zero. Their positive part consequently totals at least $N{\delta }^2/144$. Since all block lengths total $n$, some block has $S_P/|P|\ge N{\delta }^2/(144n)\ge {\delta }^2/72$. Its density of a finite subset is at least $\alpha +{\delta }^2/72\ge \delta (1+\delta /72)$.

For the remaining $3\le n<N_0(\delta )$, divide $I$ into disjoint consecutive triples and a remainder of at most two points. A three-term-arithmetic progression-free $A$ uses at most two points of each triple, so $\alpha \le 4/5$; the largest ratio occurs at $n=5$. Any singleton set from $A$ then has density of a finite subset one, which is at least $\delta +{\delta }^2/72$. We may therefore use the explicit constantsIn the large case the constructed arithmetic progression has length at least $c_1\sqrt{n}$; in the small case its length one does too. Thus these constants prove the intended result for all odd integers $n\ge 3$.

Extend the Dirichlet character $\chi$ periodically to all integers, putting $\chi (n)=0$ when $(n,N)>1$. Its Dirichlet L-function, initially on $\mathrm{Re}s>1$, isThe Euler product follows from unique prime factorization and absolute convergence; a Dirichlet character is completely multiplicative on this extension. Write ${\chi }_0$ for the principal Dirichlet character, equal to one on units and zero elsewhere.

For a nonprincipal Dirichlet character $\chi$, character orthogonality gives ${\sum }_{a=1}^N\chi (a)=0$. Explicitly, multiplication by a unit $u$ with $\chi (u)\ne 1$ permutes the unit residues and multiplies this sum by $\chi (u)$, forcing it to vanish. For $t>0$ setThe numerator is $O(t)$ at zero and the denominator is $Nt+O(t^2)$, so $H_{\chi }$ is bounded, indeed analytic, near zero; it decays exponentially at infinity. Initially for $\mathrm{Re}s>1$, absolute convergence justifiesThis Mellin transform integral is holomorphic for $\mathrm{Re}s>0$, locally uniformly in $s$, and division by the Gamma function proves the requested analytic continuation to the left of the line one.

In fact, the same argument proves Mellin continuation of a nonprincipal Dirichlet L-function to the entire plane. If $H_{\chi }(t)={\sum }_{r=0}^M{c}_r{t}^r+O(t^{M+1})$ at zero, subtract this Taylor polynomial on $(0,1)$ and add its explicit integrals:The last integral is holomorphic on $\mathrm{Re}s>-M-1$. Its possible simple poles at nonpositive integers cancel against zeros of $1/\Gamma (s)$. Letting $M$ increase shows that $L(\chi ,s)$ is an entire function, without any primitivity assumption.

For real $s>1$, use the absolutely convergent Euler product logarithmThe higher-power remainder has the uniform estimateFor a nonprincipal Dirichlet character $\chi$, invoke the allowed nonvanishing of a nonprincipal Dirichlet L-function at one. Its holomorphy and nonvanishing give a holomorphic logarithm on a small disk about one. On the connected real interval $1<s<1+\eta$, $B_{\chi }(s)$ differs from this logarithm by a fixed element of $2\pi i\mathbb{Z}$: the difference is continuous with exponential one. Thus the prime-character sum near one is bounded. This branch argument is needed for complex-valued Dirichlet characters.

For ${\chi }_0$,The finite product has a positive limit as $s\downarrow 1$, and the residue-one pole of the Riemann zeta function givesHere $O(1)$ for nonprincipal Dirichlet characters means bounded complex magnitude.

Finally, for a residue class $a$ coprime to $N$, Orthogonality of Dirichlet characters givesOnly primes not dividing $N$ occur, so the character orthogonality applies to every term. This sum diverges as $s\downarrow 1$. A finite collection of primes would give a bounded sum, a contradiction. Every reduced residue class contains infinitely many primes. This is the Dirichlet theorem on primes in arithmetic progressions; the coprimality hypothesis is essential.

For any vector $y\in {\mathbb{F}}_2^n$, use its Hamming weight $w(y)=\#\{j:y_j=1\}$. The stated product identity also follows directly by summing each coordinate independently:For $t\ne 0$, interchange the two finite sums with $u=s/t$. Character orthogonality evaluates the inner sum over codewords, whereas the product identity evaluates the sum over all binary vectors. ThusMultiply by $t^n$ to obtain the MacWilliams identity in the paper's weight-enumerator convention:Both sides are polynomials, so equality for $t\ne 0$ extends to $t=0$ as well; the intermediate quotient is not a restriction on the final identity.

A linear code of length $n$ and rank $k$ is a $k$-dimensional linear subspace of ${\mathbb{F}}_2^n$. The Hamming weight of a vector counts its nonzero coordinates. Thus the sum of the coefficients of the weight enumerator is the number of codewords:Since the zero vector is the unique word of weight zero, $W_C(0,1)=1$. Symmetry of the enumerator therefore implies $W_C(1,0)=1$. Conversely $W_C(1,0)=1$ means that the all-one vector $1$ belongs to $C$. Translation $x\mapsto x+1$ is then a bijection of $C$ which replaces weight $j$ by $n-j$, proving the polynomial symmetry. For length zero the same conclusion holds with the unique empty vector.

The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for every }x\in C\}$, using the standard bilinear form over ${\mathbb{F}}_2$. If $y\in C^{\perp }$, each summand of the character sum equals one. Otherwise choose $x_0\in C$ with $x_0\cdot y=1$; replacing $x$ by $x+x_0$ permutes the summands and reverses their sign. The sum equals its own negative and must be zero. ConsequentlyThis is character orthogonality for the additive group of the code.

Suppose $\chi$ is an irreducible character of a group of odd order and $\chi =\overline{\chi }$. Write $d=\chi (1)$. Every nonidentity element pairs with its distinct inverse, since there is no element of order $2$. Also $\chi (g^{-1})=\overline{\chi (g)}=\chi (g)$. If $\chi$ were nontrivial, character orthogonality with the trivial character of a representation would givewhere $A$ is the sum of one character of a representation value from each inverse pair. This $A$ is an algebraic integer, so $A=-d/2\in \mathbb{Q}$ is an integer. Hence $d$ is even.

But an irreducible character degree divides the group order, so $d$ must be odd. One quick justification of that divisibility is that the central class sum of a conjugacy class $C$ acts by the algebraic integer ${\lambda }_C=|C|\chi (g_C)/d$. Its integrality follows from its integer matrix on the regular group representation. Character orthogonality then givesa rational algebraic integer, hence an integer. The parity contradiction proves $\boxed{\chi =1_G}$: the trivial character is the only self-conjugate irreducible character of an odd-order group.

Write $x=g^{-1}h$ and $S(x)={\sum }_{\chi \in \hat{G}}\chi (x)$, where $\hat{G}$ is the character group of a finite abelian group. The Fundamental theorem of finitely generated abelian groups writes the finite group $G$ as a product of cyclic groups. A character of a cyclic group factor of order $r$ is determined by an arbitrary $r$th root of unity, so $|\hat{G}|=|G|$. This description also shows that the characters separate points: if $x\ne 1$, a nonzero coordinate of $x$ is detected by a character $\psi$ with $\psi (x)\ne 1$.

Multiplication by $\psi$ permutes $\hat{G}$, soFor $x\ne 1$ this forces $S(x)=0$. For $x=1$ every summand is one. Since $\chi (g{)}^{-1}\chi (h)=\chi (g^{-1}h)$, the character-sum cancellation lemma givesAll character values are roots of unity, so inversion here is also complex conjugation. This is the finite-abelian version of character orthogonality.

By character orthogonality, the squared multiplicities are the character inner product norm of the restriction of a character:Since $\chi$ is an irreducible character, its norm on $G$ is one, and henceThe omitted summands are nonnegative, so the character restriction norm bound is an equality precisely when

Write the finite abelian group additively. Its group shift operator isThese unitary operators form the regular representation and commute. The representation-theoretic facts we use are that every irreducible representation of a finite abelian group is one-dimensional, there are $|G|$ such characters of a representation, and their character orthogonality gives an orthonormal basis of functions on $G$. Each linear character here is a group homomorphism $\chi :G\to U(1)$, with $|\chi (g)|=1$.

For $\chi \in \hat{G}$, the character group of a finite abelian group, putChanging variables to $u=g+h$ givesThe $|G|$ vectors $|v_{\chi }⟩$ are therefore a common eigenbasis. Using $\chi (g)$ instead of its complex conjugate in their definition reverses every eigenphase; this is merely the quantum Fourier transform sign convention.