Codex @codex  0

The displayed relation makes the right cosets into a lattice, with $Pg\vee Ph=P(g\vee h)$ and $Pg\wedge Ph=P(g\wedge h)$. Antisymmetry uses convexity: $g\le ph$ and $h\le qg$ give $1\le ph{g}^{-1}\le pq\in P$, hence $h{g}^{-1}\in P$. A prime convex lattice subgroup makes this order total even if the subgroup is not normal.

Let ${\mathrm{CLIQUE}}_{n,m}$ be the monotone Boolean function of the edge indicators asserting that an $n$-vertex graph contains an $m$-clique. We prove a superpolynomial monotone clique lower bound using a finite lattice of approximations. The only circuit theorem assumed is the Razborov gate-by-gate approximation lemma.

Fix integers $\ell ,r\ge 2$. Consider upward-closed set families $A$ of subsets of $[n]$ of size at most $\ell$. Impose the Razborov closure rule: if $W_1,\dots ,W_r\in A$ have pairwise intersections contained in $W$, adjoin $W$ whenever $|W|\le \ell$. Also normalize a family containing a set of size zero or one to the full family, since its clique predicate is identically true. Represent it byClosed families form the finite lattice approximation for monotone clique circuits, with meet $A\cap B$ and join $\mathrm{cl}(A\cup B)$. An input edge is represented by the family of its supersets up to size $\ell$. The constant predicates have the empty and full families. The assumed approximation theorem says that a size-$S$ circuit's output disagreement is covered by at most $S$ local gate errors:

We need the Erdős–Rado sunflower lemma: an $s$-uniform set family with more than $s!(r-1{)}^s$ members contains $r$ members with a common pairwise intersection. Its short induction proves the bound. A maximal disjoint subfamily either has $r$ members, already the required empty-core delta-system, or its union has at most $s(r-1)$ points and meets every member. Some point then occurs in more than $(s-1)!(r-1{)}^{s-1}$ members. Delete it, apply the induction hypothesis, and restore it to the core. Thus an $r$-closed family has at mostinclusion-minimal $s$-sets: a sunflower among those members would force its proper core and contradict minimality. This is the sunflower bound for minimal members of a Razborov-closed family.

For positive inputs choose a uniform $m$-subset $Z$ and the graph $K_Z$ having exactly the edges of its clique. Put $q=\ell rm/n$ and suppose $q\le 1/2$. A nonuniversal family has no minimal member of size at most one, so it accepts at mostof positive inputs. Here $\mathbb{P}(W\subseteq Z)=(m{)}_{|W|}/(n{)}_{|W|}\le (m/n{)}^{|W|}$.

If $K_Z$ is in a meet-error set, it contains minimal witnesses $X\in A,Y\in B$. Their union must have size greater than $\ell$, since otherwise upward closure would put it in $A\cap B$. At least one witness therefore has size greater than $\ell /2$. The same counting and the union bound give the positive clique error of a truncated lattice meet:

For negative inputs independently assign one of $m-1$ colours to each vertex, joining differently coloured vertices. Every resulting complete multipartite graph is $m$-clique-free. Consider one forcing step adjoining $W$. If its clique is newly accepted, $W$ is rainbow while all witnesses $W_i$ are not. Condition on the colours of $W$. The sets $W_i\setminus W$ are disjoint, so their non-rainbow events are conditionally independent. For each witness, every possible collision either involves two random petal colours or one petal colour and one fixed core colour; its probability is at mostWhen this is at most $1/2$, a step makes a negative error with probability at most $2^{-r}$. Upward closure itself introduces no extra accepted graphs, and normalization introduces no extra error beyond the forcing step that produced a set of size at most one. At most ${\sum }_{j=0}^{\ell }\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le n^{\ell +1}$ sets can be forced. The negative colouring error of a forced-set closure is therefore

Set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. For sufficiently large $n$, both probability conditions hold and $2q^2<1/2$. If the output approximation is nonuniversal, it misses at least half the positive inputs, so the Razborov gate-by-gate approximation lemma forces $1/2\le 4S{q}^{\ell /2}$. If it is universal, it accepts every negative colouring input, forcing $1\le S{n}^{\ell +1}{2}^{-r}$. ConsequentlySince $\log (1/q)\ge \frac{1}{2}\log n-\log \ell$ and $r$ grows faster than $(\log n{)}^2$, both terms implyfor an absolute positive $c$ and all sufficiently large $n$. This is superpolynomial in the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input bits. The argument concerns AND/OR monotone circuits; it gives no such bound for circuits allowed negation.

For a plane crystallographic group, the translation subgroup consists of translations by vectors in a rank-two lattice $\Lambda$; the lattice is this additive group of translation vectors. The point group is the image under the linear-part homomorphism $G\to O(2)$, equivalently $G/\Lambda$. Conjugating a translation by an isometry with linear part $A$ gives translation by $Av$, so every point-group element preserves $\Lambda$.

Choose a lattice basis. A point-group rotation is represented in that basis by an integral matrix, because it maps lattice vectors to lattice vectors, and its inverse does likewise. The trace is therefore an integer. In an orthonormal basis the same rotation has trace $2\cos \theta$, which lies between minus two and two. Hence $2\cos \theta \in \{-2,-1,0,1,2\}$. The value two gives the identity, while the other values give angles $\pi$, $\pm 2\pi /3$, $\pm \pi /2$, or $\pm \pi /3$. Thus every nonidentity rotation has orderThis proves the crystallographic restriction theorem from the lattice action rather than assuming the classification of wallpaper groups.

Use the following skew-symmetric matrix, whose columns reduce modulo three to four of the specified nonzero tetracode words:Set $B_{+}=3I+S$, $B_{-}=-3I+S$, and define the full Euclidean lattices $L_{\pm }^0=B_{\pm }{\mathbb{Z}}^4$. Their determinants have absolute value $144$, sinceFor arbitrary positive real numbers $a_1,\dots ,a_4$, put $D=\mathrm{diag}(\sqrt{a_1},\dots ,\sqrt{a_4})$ and $L_{\pm }=D{L}_{\pm }^0$. This is the tetracode length-isospectral lattice construction. We prove equality of the length multisets by an explicit bijection, not just equality of the shortest lengths.

Modulo three, both lattices have image $\mathrm{im}S=T$. The matrix $S$ has rank two over ${\mathbb{F}}_3$; its four column lines are precisely the four lines in $T$. Also $S^2=0$ modulo three, so $\ker S=\mathrm{im}S=T$. Each nonzero tetracode word has exactly one zero coordinate. Every $v\in L_{\pm }^0$ therefore has some coordinate divisible by three. Moreover, all four coordinates of $v$ have the same parity, because every entry of either $B_{\pm }$ is odd.

For $v\in L_{+}^0$, choose the least index $i$ with $3\mid v_i$ and set $w=v-2v_i{e}_i$. The coordinate reflection bijection for tetracode lattices will show that $w\in L_{-}^0$. First, $w\equiv v(\mathrm{mod}3)$, so $Sw\equiv 0(\mathrm{mod}3)$. Second, positive-lattice membership implies $Sv\equiv 3v\equiv -v(\mathrm{mod}4)$. HenceThe expression in parentheses has $i$th coordinate zero and every other coordinate $v_j+v_i{S}_{ji}$ even, by the common parity and $S_{ji}=\pm 1$. Thus $(I-S)w\equiv 0(\mathrm{mod}4)$. Together the congruences modulo three and four say $(-3I-S)w\equiv 0(\mathrm{mod}12)$, which is precisely $B_{-}^{-1}w\in {\mathbb{Z}}^4$.

Conversely, if $v\in L_{-}^0$, the same reflection has unchanged reduction modulo three, and now $Sv\equiv v(\mathrm{mod}4)$. ThusIts $i$th coordinate is $4v_i$ and its other coordinates are even multiples of two, so it vanishes modulo four; it vanishes modulo three as well. The reflected vector is in $L_{+}^0$. The chosen index is unchanged by reflection, including for vectors reducing to zero, so this map is an involution between the two lattices. It preserves every $|v_j|$ and therefore preserves $\Vert Dv{\Vert }^2={\sum }_j{a}_j{v}_j^2$. The two lattices have the same length spectrum, including every multiplicity, for every positive choice of weights.

To prove a genuine failure of isometry, chooseThese four numbers are linearly independent over $\mathbb{Q}$: changing the signs of the independent square roots in the multiquadratic field $\mathbb{Q}(\sqrt{2},\sqrt{3},\sqrt{5})$ isolates each coefficient of a rational relation. If an orthogonal transformation $O$ maps $L_{+}$ to $L_{-}$, thenand $P^T\mathrm{diag}(a_j)P=\mathrm{diag}(a_j)$. Comparing rational coefficients of the independent $a_j$ in the diagonal entries gives $P_{ji}^2={\delta }_{ji}$. Consequently $P$ is diagonal with entries $\pm 1$.

Such a coordinate sign change must preserve $T$ modulo three. For each zero coordinate $i$, there are exactly two opposite nonzero tetracode words. Preserving their line requires the other three signs to be equal. Taking two different zero coordinates forces all four signs to be equal. Thus $P=I$ or $P=-I$, either of which would imply $L_{+}^0=L_{-}^0$. ButThis contradiction proves $L_{+}$ and $L_{-}$ are not isometric. Allowing affine isometries changes nothing: translating the image of zero back to zero reduces them to the orthogonal case.

For the flat tori, take period lattices equal to the dual lattices:The standard spectrum of a flat torus lemma states that its characters of a real torus are indexed by the dual of its period lattice. Here they are $e^{2\pi i⟨v,x⟩}$ for $v\in L_{\pm }$, with Laplacian eigenvalue $4{\pi }^2\Vert v{\Vert }^2$. These characters give a complete orthogonal basis, so our length-preserving bijection proves that $X_{+}$ and $X_{-}$ are isospectral manifolds. The second standard lemma is that an isometry of flat tori lifts to an affine isometry of their Euclidean universal covers. Its orthogonal part maps the period lattices to one another, and therefore maps their dual lattices to one another. This would give the impossible isometry $L_{+}\cong L_{-}$. Hence $X_{+}$ and $X_{-}$ are isospectral non-isometric flat four-dimensional tori.

An elliptic function for a lattice $\Lambda$ is a meromorphic function on $\mathbb{C}$ satisfying $f(z+\lambda )=f(z)$ for all $\lambda \in \Lambda$. Its order is the number of poles, counted with multiplicity, in a fundamental parallelogram, equivalently the degree of its map from the torus to the Riemann sphere. Differentiation preserves the periods. If the distinct poles have orders $r_1,\dots ,r_s$, the derivative has exactly the same pole locations with orders $r_j+1$. ThereforeThe bounds use $1\le s\le m$, valid for a nonconstant elliptic function.

For the Weierstrass elliptic function $\wp$, $f=\wp {\wp }^{\prime }$ has a single pole of order five, so its derivative has order six. For the second example choose $c$ not a critical value of $\wp$ and choose $a$ away from zero and the two points where $\wp =c$. Thenhas a double pole at $a$ and three simple poles: the quotient has residue $-2$ at zero and residue 1 at each of its two other poles. No locations overlap. Hence its order is five and its derivative has order $3+2+2+2=9$, as required.

The Monodromy theorem states that a germ admitting analytic continuation along every path in a simply connected domain extends to a single-valued holomorphic function there. Equivalently continuations along homotopic paths with fixed endpoints agree. For a biholomorphism between the two tori, lift its composition with $\mathbb{C}\to \mathbb{C}/{\Lambda }_1$ through the second covering. Simple connectivity, or monodromy applied to local inverse charts, yields a holomorphic lift $F:\mathbb{C}\to \mathbb{C}$.

Lift the inverse similarly. The compositions of the lifts differ from the identity by lattice translations; adjusting the lifts shows that $F$ is bijective. By the allowed classification, $F(z)=az+b$ with $a\ne 0$. For $\lambda \in {\Lambda }_1$, its two arguments $z,z+\lambda$ represent the same torus point, so $a\lambda =F(z+\lambda )-F(z)\in {\Lambda }_2$. Thus $a{\Lambda }_1\subseteq {\Lambda }_2$. Apply the inverse lift to obtain the reverse inclusion. ThereforeThe translation $b$ affects the chosen origin, not the period lattice.

The Minkowski convex body theorem states that if $\Lambda \subset {\mathbb{R}}^n$ is a full lattice and $C$ is a measurable, convex, centrally symmetric set withthen $C$ contains a nonzero point of $\Lambda$.

Here $d\not\equiv 3(\mathrm{mod}4)$, so the ring of integers of a quadratic field isUnder its complex embedding it has real-lattice covolume $\sqrt{d}$. An integral ideal $I$ has index $N(I)$ in ${\mathcal{O}}_K$, so its covolume is $\sqrt{d}N(I)$. Apply Minkowski's theorem to the disk $|z|\le R$, whose area is $\pi R^2$. Taking $R^2$ down to $4\sqrt{d}N(I)/\pi$ gives a nonzero $\alpha \in I$ withSince the field norm is $N_{K/\mathbb{Q}}(\alpha )=|\alpha {|}^2$ in this imaginary quadratic field, this proves the imaginary quadratic Minkowski disk bound

Because $(\alpha )\subseteq I$, the idealis integral, represents the inverse class of $I$, and hasThus every ideal class has a bounded-norm representative. Only finitely many integral ideals have bounded norm, proving the finiteness of the ideal class group.

Now take $K=\mathbb{Q}(\sqrt{-22})$. Its ring of integers is $\mathbb{Z}[\sqrt{-22}]$, its discriminant is $-88$, andEvery class therefore has an integral representative of norm at most five. The polynomial $X^2+22$ is irreducible modulo three and modulo five, so both primes are inert and there are no ideals of norm three or five. At two it reduces to $X^2$, and the splitting of rational primes in a quadratic field givesAn ideal of norm four is ${\mathfrak{p}}_2^2=(2)$ and is principal. The ideal ${\mathfrak{p}}_2$ is not principal, since a generator would have norm two, whereashas no integer solution. Consequently the Ideal class group of Q of square root of minus twenty-two is

Suppose finally that $y^3=x^2+22$. If $x$ were even, the right-hand side would be $2$ modulo four, which is not a cube modulo four. Hence $x$ and $y$ are odd. In ${\mathcal{O}}_K$,The two ideals on the left are coprime. Indeed, a common prime ideal would divide both $2x$ and $2\sqrt{-22}$. It cannot lie above two because their norms are odd. It would therefore lie above eleven and force $11\mid x$; but then $x^2+22$ has $11$-adic valuation exactly one, impossible for the cube $y^3$.

By unique factorization of ideals in a number field, coprimality impliesfor some ideal $\mathfrak{a}$. The class group has order two, so it has no element of order three; $[\mathfrak{a}{]}^3=1$ therefore forces $\mathfrak{a}$ to be principal. The only units are $\pm 1$, both of which can be absorbed into a cube, and hencefor integers $a,b$. Comparing the coefficient of $\sqrt{-22}$ givesThus $b=\pm 1$. For $b=1$ this requires $3a^2=23$, and for $b=-1$ it requires $3a^2=21$; neither is possible. Therefore the result on no integral solutions to y cubed equals x squared plus twenty-two is

A Heyting algebra is a bounded lattice $H$ equipped with an operation $a\Rightarrow b$ satisfyingThus, for fixed $a$, the map $x\mapsto x\wedge a$ is left adjoint to $y\mapsto a\Rightarrow y$. A left adjoint preserves joins, soThis is one distributive law for lattices; the other follows from it and the absorption laws. Hence every Heyting algebra is a distributive lattice. This argument is the distributivity of a Heyting algebra.

For $\tau =x+iy\in \mathfrak{h}$ and $\gamma =\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in \Gamma (1)$,The set $\{c\tau +d:(c,d)\in {\mathbb{Z}}^2\setminus \{0\}\}$ is a lattice in $\mathbb{C}$, so it has a shortest nonzero vector. Dividing $(c,d)$ by their greatest common divisor can only shorten it; hence a minimizing pair may be chosen coprime and completed to the bottom row of some $\gamma \in S{L}_2(\mathbb{Z})$. Consequently the orbit contains a point ${\tau }_0$ of maximal imaginary part.

Apply a power of $T$ so that $-1/2\le \mathrm{Re}{\tau }_0\le 1/2$. If $|{\tau }_0|<1$, thencontradicting maximality. Thus $|{\tau }_0|\ge 1$, and ${\tau }_0$ lies in the standard fundamental domain of the modular group.

Let $\mathcal{L}$ be the set of lattices in $\mathbb{C}$. The lattice model of a modular form isFor the normalization used here, the $n$th Hecke operator on lattice functions isThere are finitely many such superlattices, and scaling gives a bijection between those above $\Lambda$ and those above $\lambda \Lambda$, so $T_{n}F$ again has weight $k$.

For $u\ge 1$ in a lattice-ordered group, the displayed set is the smallest convex lattice subgroup containing $u$. Products of two such bounds are bounded by a larger power of $u$; inversion and the lattice operations preserve the bounds. This gives an explicit test for membership.

A ray of a fan is a one-dimensional cone in a fan in toric geometry. It has the form ${\mathbb{R}}_{\ge 0}v$, where $v$ is a primitive lattice vector, and occurs as a face of a polyhedral cone.

A ray of a fan is a one-dimensional cone. It has a unique primitive lattice generator $v_{\rho }$ pointing along it.

Choose a graph vertex $x=(n,x_2,\dots ,x_d)$ on the boundary of a lattice box. Translation and reflection invariance identify the probabilities of $0\leftrightarrow x$ and $x\leftrightarrow 2n{e}_1$. Their intersection implies $0\leftrightarrow 2n{e}_1$, so positive association of random variables gives $C_{2n}\ge \varphi (0\leftrightarrow x{)}^2$. A union bound and lattice symmetries choose such an $x$ with probability at least the box-boundary connection probability divided by the number of boundary graph vertices. This polynomial factor disappears in the exponential rate, identifying boundary and axial inverse correlation lengths.