A CW complex is built by attaching q-dimensional discs to the -skeleton along maps of their boundary spheres, with the closure-finite and weak-topology conditions. Write for its q-skeleton and . The cellular chain group is
The cellular boundary is the composite of the connecting map and the relative quotient map:
Consecutive maps in the relevant exact sequences compose to zero, so these maps make a cellular chain complex. Equivalently, a boundary coefficient is the degree of the attaching sphere followed by collapse onto the sphere of a selected lower cell. Its cellular homology is . The relative groups of successive skeleta vanish off their cell dimension; their exact sequences identify this homology with singular homology, the cellular homology theorem.
For , the sphere has a zero-cell and a k-cell with zero boundary. The Complex projective space has one cell in each dimension and no odd cells, so all cellular boundaries vanish. Consequently
At , the sphere consists of two points and ; at , projective space is a point.
Put and . Its product CW complex has cells in dimensions . For , these positive dimensions are distinct and never consecutive, so all cellular boundaries vanish. Thus
Its -skeleton is . Collapsing it gives the quotient
It induces an isomorphism on top homology, with degree after choosing the quotient orientation. Let be the Hopf fibration and set , the Hopf projection of a product smash quotient.
On reduced homology, the collapse kills the two lower-dimensional classes, and the remaining top class maps to zero because projective space has no odd-dimensional homology. Therefore in every reduced degree. On homotopy groups, for , with summands induced by the two factor inclusions. Both inclusions are collapsed by , so and hence vanish on both summands. The domain is simply connected and connected, which also handles the lower groups.
It remains to prove that is not null-homotopic. The Hopf fibration has fibre and has the homotopy lifting property for the CW domain : a homotopy downstairs and a lift of its initial map have a lift with that specified initial value. If were homotopic to a constant, lift this homotopy starting at . The ending map would land in the single fibre . Every map is null-homotopic, since the simply connected domain permits its lift to the contractible universal cover . Thus would be null-homotopic in , contradicting its nonzero top homology map. Hence
A chain complex consists of abelian groups and homomorphisms with . Its groups of chain cycles and chain boundaries are and ; the identity ensures . Its homology groups are
For a nonnegative complex, take for .
The singular chain group is the free abelian group on continuous maps , called singular simplices. With the inclusion of the face opposite vertex , define
Deleting any two vertices in the two possible orders gives the same face with opposite signs, proving . This defines the singular chain complex and its singular homology. A continuous map induces the chain map ; it commutes with the boundary because composition commutes with restriction to faces.
To prove homotopy invariance of homology, let have endpoints . Triangulate by the simplices with ordered vertices
Let be their affine parameterizations. The singular prism operator is
On taking boundaries, shared internal faces of consecutive prism simplices cancel. The top and bottom faces give , and the remaining faces are with their induced signs. Thus
For a chain cycle , is a chain boundary, so on homology. If is a homotopy equivalence, its homotopy inverse therefore induces an inverse to , proving that singular homology depends only on homotopy type.
Use the standard CW complex for an orientable genus-three surface: one vertex, six edges , and a two-cell whose attaching word is . The cellular homology theorem identifies this cellular calculation with singular homology. The boundary of every edge is zero, and each edge's total exponent in the attaching word is zero, so the two-cell boundary is zero. Hence
Choose to be the nonseparating curve represented by , and choose as a small circle bounding a disc in a surface patch. Then is a nonzero primitive homology class, whereas the inclusion of induces zero on . If a homotopy equivalence carried onto , its restriction would factor through and kill , contradicting injectivity on first homology. This is the homology obstruction to carrying surface curves onto one another.
There is nevertheless such a continuous map. Map the edge homeomorphically onto and all other edges to its base point. The two-cell attaching word then has winding number zero in , hence is null-homotopic and the map extends to . Compose with a homeomorphism and the inclusion of in the surface. This gives . Thus an arbitrary map can carry the first curve onto the second, but a homotopy equivalence cannot.
For an unambiguous drawing, realize as the double of a manifold formed from a disc with three holes. Its two copies are glued along all four boundary circles. The red curve below follows an arc from the outer boundary to the first hole on the front copy and returns along the matching arc on the back copy; it is a nonseparating curve. The blue circle is entirely in a disc patch on the front copy and is contractible.
Figure 1.
Nonseparating and contractible circles on the genus-three surface, drawn as a doubled three-holed disc
. Details.
Fix an elliptic curve with origin and a Weierstrass equation of an elliptic curve. Define the naive logarithmic -height by for and . The -map has degree two and pulls the projective hyperplane bundle back to . Thus
is a Weil height machine representative for the symmetric ample line bundle . This factor of one half fixes the convention for the normalized height on an elliptic curve used below.
The Theorem of the Cube gives the quadratic geometric identities. Pull its alternating line-bundle identity back along and use . For the addition and subtraction maps , this gives
On heights, therefore,
uniformly on . In particular, restriction to the diagonal gives and a uniform constant with . The general multiplication formula is : the cube identity applied to gives a second-difference recurrence, whose initial classes are and in the Picard group.
Define the canonical height of an elliptic curve by
The existence and bounded comparison are elementary: consecutive terms differ by at most , so their telescoping series converges and
The bound is uniform in , and the limit is nonnegative. Shifting the index gives . This is the unique function within bounded distance of with that doubling rule: the difference of two such functions at is times their bounded difference at , and hence zero. A change of Weierstrass model changes the naive height only by a bounded function, so the normalized limit is independent of that model.
Apply the approximate parallelogram identity to , divide by , and pass to the limit. The bounded error disappears, yielding the exact height parallelogram identity
Evenness follows already from . The second-difference recurrence along , with initial values at , consequently gives for every integer . The arithmetic cube identity from 2(i), scaled in the same way, also becomes an exact third-difference identity for .
The canonical height pairing
is symmetric and biadditive: the difference is half the vanishing third difference. Its diagonal is . Positivity gives the Cauchy-Schwarz inequality for this pairing without first assuming finite generation. Indeed for integers ; dividing by and using density of rational shows that the associated quadratic polynomial is nonnegative on the real line. Its discriminant therefore gives .
The Northcott theorem and the bounded comparison make finite. The map has finite fibres, so bounded -height indeed controls the number of points, including . This proves the important criterion
For a torsion point the integer quadratic rule gives zero. Conversely, height zero makes all belong to one finite bounded-height set; two coincide, forcing for some . This argument also proves torsion finiteness over the fixed number field.
The normalized height is functorial for an isogeny of elliptic curves :
The pullback of has degree and is symmetric. Its difference from that many copies of is a symmetric degree-zero line bundle, hence a two-torsion Picard class. Its height is bounded, so the ordinary height relation has a bounded error. Commuting the isogeny with and taking the normalized limit removes that error. This explains the natural quadratic scaling under multiplication and the usefulness of normalized heights in comparing isogenous curves.
Here is their role in the Mordell-Weil theorem. The separate arithmetic input is the Weak Mordell-Weil theorem, asserting finiteness of . One route uses the Kummer exact sequence of an elliptic curve to inject this quotient into . The division torsors are unramified outside finitely many places containing those over and those of bad reduction. After a finite Galois extension splitting , their classes are pairs of square classes with even valuations outside this finite set. These square classes form a finite group: the obstruction to being represented by an S-unit lies in the finite ideal class group's two-torsion, and the S-unit group is finitely generated, hence finite modulo squares. The inflation-restriction kernel is a cohomology group of a finite group with finite coefficients, also finite. This supplies the finite quotient without using the full theorem in advance.
Choose representatives for that finite quotient and put . Every point has the form . Nonnegativity and the exact parallelogram identity give
If , this decreases the height by more than . Repeating must reach the finite set . Unwinding the halving expressions writes the initial point as an integer linear combination of the and a point of . Thus is finitely generated, the canonical-height proof of Mordell-Weil finite generation. The normalized height supplies the descent and Northcott supplies its finite endpoint; neither by itself supplies the weak theorem's finite quotient.
After finite generation, is a finite torsion subgroup plus a free abelian group of finite rank. The canonical height pairing is positive-definite on the associated real vector space. To justify the latter rather than assuming it, if its nonnegative quadratic form had a real null direction, rounding longer and longer multiples of that direction to lattice points would produce infinitely many points of bounded height: the null-direction cross terms vanish, leaving only uniformly bounded rounding errors. This contradicts Northcott finiteness. Hence the free part is a Euclidean height lattice. Heights can consequently bound point searches, certify independence through positive Gram determinants, and organize the arithmetic complexity of rational points.
Let be a number field of degree , and normalize its absolute values so that the product formula is for , where ; at a complex place use the ordinary modulus with weight two. For , define
Only finitely many factors differ from one. Rescaling all coordinates multiplies the local maxima by , whose weighted product is one, so the projective height is well-defined. It is at least one by comparison with any nonzero coordinate. On enlarging to , the identity makes the normalized product unchanged. Thus this is an absolute height on algebraic projective points. For coprime rational integer coordinates it is simply their maximum absolute value.
For a projective variety and an embedding , take . Changing the basis of the same projective linear system changes the height by a bounded amount: the coordinate transformation and its inverse have fixed local coefficient bounds, equal to one outside finitely many places. If is ample and is very ample, set for an embedding from , up to a bounded function. A general line bundle can be written with both and very ample, defining its height as the difference of their embedding heights.
This is the Weil height machine, with
The first relation follows from the Segre embedding, whose local maximum is the product of the two maxima; tensor powers similarly use the Veronese embedding. The second follows by pulling back the defining sections. These constructions make the choices equivalent modulo bounded functions. For a fixed homogeneous morphism with no base point, upper local height bounds come from its coefficients, and lower bounds from the Projective Nullstellensatz expressing coordinate powers in the ideal of its defining forms. The constants are one outside a finite set of places. This gives the uniform bounded errors and shows why heights belong to line-bundle classes rather than being independent of every projective embedding.
The Northcott lemma states that for fixed and , the algebraic points of with and form a finite set. In particular the -rational points of bounded projective height are finite. Here is a proof, including the degree bound.
First let have degree and . Write its primitive minimal polynomial as , with positive integer . The height-Mahler measure formula is
Its finite-place part follows from multiplicativity of the nonarchimedean polynomial coefficient norm: a primitive integer polynomial has norm one at each prime, so factoring it bounds the product of the roots' local maxima by the inverse leading-coefficient norm. The archimedean part is the displayed product over conjugates. Combining them with the product formula gives the identity.
Expanding the polynomial now bounds each integer coefficient by
There are finitely many degrees and finitely many such integer coefficient lists, each with finitely many roots. Hence there are only finitely many possible . This proves the minimal-polynomial coefficient proof of Northcott finiteness for algebraic numbers.
On the projective chart , each ratio has degree at most the point's field degree and
The equality uses the product formula. Each coordinate ratio therefore belongs to a finite set, and there are finitely many charts. This proves the projective Northcott theorem. Restricting to gives the result for a chosen embedding. For an ample line-bundle height, the comparison reduces its bounded-height sets to this case.
Both qualifications matter: a degree bound cannot be dropped, since infinitely many roots of unity have height one; and the finiteness assertion need not hold for a nonample line bundle, such as the trivial bundle's bounded height on a variety with infinitely many rational points.
Choose an oriented basis of the period lattice, so . The Weierstrass elliptic function is constructed by the normally convergent series
On compact sets away from the lattice the summands are , which is summable over a plane lattice. It is even, has double poles at the lattice with zero residues, and is periodic. To check periodicity without splitting divergent series, differentiate termwise: is invariant under lattice shifts. Hence is constant; evenness evaluated at makes this constant zero.
The Weierstrass sigma function is the canonical product
Its logarithmic tails are likewise , so it defines an entire function with simple zeros exactly at the lattice and . Pairing opposite lattice factors makes it odd. Its logarithmic derivative is the Weierstrass zeta function
Thus is constant. Integrating this identity and evaluating the sigma ratio at gives
Integration of zeta around a fundamental cell, containing one pole of residue one, gives the Legendre relation for Weierstrass quasi-periods . These formulas explain why sigma itself is not an elliptic function, but balanced products of translates can be.
For completeness, the basic algebraic property of wp is , where and . The identity follows by canceling the principal parts using the Laurent expansion: the difference is an entire elliptic function, hence constant, and its constant term is zero. The discriminant is nonzero; equivalently the three half-period values are distinct. These properties lead to the cubic embedding in 2(ii).
Now let be a nonzero meromorphic function on the torus and lift it to a periodic meromorphic function on the plane. Its logarithmic derivative is periodic. Choose a fundamental parallelogram with no zero or pole on its boundary. The residue theorem applied to gives equality of the total zero and pole multiplicities. Applied to , it gives the difference of the sums of the zero and pole lifts. Pairing opposite edges explicitly yields
Each integral of on the right is times an integer, since its endpoint values of coincide and the image path avoids zero. Therefore the zero sum and pole sum agree in .
Conversely, suppose the point sums agree modulo the lattice. Change one chosen lift of a point by a lattice element so the two sums agree exactly in ; this changes no point of the torus. Then
has the prescribed divisor. Its multiplier under either basis period is , so it descends to the torus. Repetitions contribute their appropriate multiplicities. This proves the principality criterion on a complex elliptic curve:
There is an implicit qualification in the wording about separate zero and pole divisors: their supports must be disjoint. If a point occurs on both lists, cancel common multiplicities first when prescribing the divisor difference. A function cannot simultaneously have a zero and a pole at the same point; for example identical one-point lists satisfy the sum condition but do not specify separate zero and pole divisors. For , any nonzero constant supplies the empty divisor.
A Levi-Civita connection is a connection on the tangent bundle which is torsion-free and compatible with the Riemannian metric. Its defining identities are
To obtain uniqueness, write the metric identity for , and , add the first two and subtract the third, and use the torsion identity to interchange the derivatives. This gives the Koszul formula
The metric is nondegenerate, so these inner products determine uniquely.
For existence, let denote the right-hand side. The bracket rules and give, by cancellation of all extra derivatives,
Thus the nondegenerate metric defines a unique smooth vector field from , and these identities give the connection rules. In coordinates the construction reads
The coefficients are smooth and symmetric in , proving zero torsion. Substituting them gives
which is exactly metric compatibility. Since the construction was given intrinsically by , the local formulas agree on overlaps. This proves existence and uniqueness of the Levi-Civita connection on every Riemannian manifold.
Define the Riemann curvature tensor by
The connection rules make this expression tensorial in all three arguments. To fix the component convention, throughout this solution use
With this convention, the unit sphere has and positive Ricci curvature. In a coordinate frame, the components are obtained from
The algebraic curvature symmetries are
together with the first Bianchi identity
The first antisymmetry follows from the definition. Metric compatibility gives , giving the second. Torsion-freeness reduces the cyclic sum to the Jacobi identity for Lie brackets of vector fields; pair interchange follows algebraically from these antisymmetries and the cyclic identity. These explain the identities rather than choosing unrelated sign conventions.
Define the Ricci curvature by the tensor contraction
This is a bilinear form, since is tensorial and trace is linear. At a point choose an orthonormal basis. Pair interchange gives
so Ricci curvature is symmetric.
For the final determination in dimension three, an algebraic curvature tensor is determined by its entries in the three unordered index pairs : antisymmetry removes repeated indices, and pair interchange makes the resulting array symmetric. It therefore has at most six independent entries. Write
The diagonal Ricci components give
so, for example, , and the other two follow cyclically. The three off-diagonal entries are also recovered explicitly:
Thus every independent curvature entry is determined by Ricci; this proves injectivity, not merely a dimension count.
An invariant formula making the reconstruction explicit is, with ,
To verify it, the right-hand side has the two antisymmetries, pair interchange and the cyclic identity by symmetry of and Ricci. Contracting its first and third indices in dimension three gives
Subtract it from the original tensor. The difference has zero Ricci contraction, and the six recovered-entry formulas above force it to vanish. This completes the proof of three-dimensional curvature from the Ricci tensor in arbitrary coordinates.
A geodesic is an affinely parametrized curve satisfying for the Levi-Civita connection of the Riemannian metric. In coordinates, write . For a vector field along the curve,
Putting gives the geodesic equation
This is a smooth second-order ordinary differential system, so the Picard-Lindelöf theorem gives local existence and uniqueness for prescribed position and velocity.
To prove local extension of geodesic velocity, first suppose . The constant curve through solves this initial value problem, so uniqueness makes constant locally. The zero vector field is the desired extension.
Otherwise choose a chart about in which the first component of the coordinate velocity is nonzero. Write the coordinate curve as and define
At its derivative has columns and is invertible, because the first component of is nonzero. The inverse function theorem therefore supplies coordinates on an open neighbourhood after shrinking the parameter interval to . Along the curve these coordinates are . The smooth coordinate field , pushed back through and the original chart, agrees with . This proves the extension without assuming that a long geodesic has no self-intersections.
By metric compatibility, differentiation along the curve gives
The local extension above permits the ordinary vector-field version of the metric identity to be used along the arc, or the same identity follows directly from the coordinate derivative. Hence an affinely parametrized geodesic has constant speed, including the zero-speed case.
Now let be the unit sphere in . Its induced Levi-Civita derivative is the tangential projection of the ordinary ambient derivative: projection preserves the metric identity, and the commuting ambient coordinate derivatives give zero torsion. By uniqueness of the Levi-Civita connection, proved in Question 5, this is the induced connection.
Thus a curve on the sphere is a geodesic exactly when its ambient acceleration has no tangential component. The normal space is spanned by , so . Differentiating twice gives and
where is the constant speed. Therefore . With initial data and , all solutions are
and, when , . The orthogonality and length conditions show directly that the displayed curve remains on the sphere, and its acceleration is , so it is indeed a geodesic. The nonconstant geodesics are the great circles traversed at any constant speed; arbitrary parameter intervals give their restrictions, and shifting the initial parameter simply shifts the formula. There are no other geodesics.
A connection on a vector bundle is a linear map with . Write a local frame as a row , and a section as with a coefficient column . If the connection one-form is the matrix , then
This fixes the matrix convention for all subsequent signs.
For an -valued differential form of degree , represented locally by a column of ordinary forms, its covariant exterior derivative is
The defining graded Leibniz rule with a scalar form of degree is
It follows by moving the one-form past , which introduces . It uniquely extends the connection on sections.
The induced endomorphism bundle connection is characterized on an endomorphism section by . For a matrix-valued form of degree , the extension is
Indeed it is exactly the formula that makes
The endomorphism-valued exterior product uses matrix composition as well as the ordinary exterior product, so factors cannot in general be interchanged.
Define the curvature form of a connection by acting on sections, or equivalently by
It is tensorial in both vector arguments and in : the derivatives of multiplying functions cancel by the connection rule. For example , since the two terms cancel and . Thus curvature is a two-form with values in the endomorphism bundle. Locally, applying the graded rule gives
so
For a change of frame of a vector-bundle connection , the coefficients satisfy , and differentiation gives
Squaring yields , precisely the transformation rule of an endomorphism-valued two-form. This independently proves that the local expressions define one global curvature form of a connection.
For the Bianchi identity, use the endomorphism formula with degree two:
Every term cancels with its indicated sign. Therefore
where here means the induced derivative on the endomorphism bundle.
For a line bundle, the endomorphism bundle is canonically the trivial scalar bundle: every fibre endomorphism is a scalar times the identity. Scalar multiplication commutes, so and the endomorphism covariant derivative on scalar-valued forms reduces to . The Bianchi identity consequently says .
If is another connection, their difference is -linear in sections because the Leibniz terms cancel. Hence is a global endomorphism-valued one-form; for a line bundle it is an ordinary global scalar one-form. Locally , so
Thus the two closed curvatures differ by an exact form, proving the connection-independent curvature class of a line bundle:
No global trivialization of the line bundle itself was assumed; it is its endomorphism bundle that has the canonical scalar identification.
A smooth right group action is a smooth map from to , with and . It is a free action of a group if implies .
A smooth principal bundle consists of such a free action and a surjective map whose fibres are the orbits, together with equivariant local trivializations
where . The trivializations are diffeomorphisms; in particular the bundle projection is a submersion.
For two such trivializations, fixes the base coordinate and is equivariant. Write . Equivariance immediately gives
The function is smooth because and are smooth. This proves the general transition function of a principal bundle formula; the multiplier is on the left, even though the original action is on the right.
For the explicit bundle, represent a point of by a nonzero vector modulo nonzero real scaling. The map sends to the complex line , so it is well-defined and surjective. Its smoothness follows from the local ratio charts below. Ordinary scalar multiplication by would not be free, since acts trivially on real projective classes. Instead define
The two possible roots differ by a real sign, so give the same class. This is independent of the real representative of . Products of chosen roots show the right action law, and the identity acts trivially. Locally on a smooth square-root branch exists; these local definitions agree projectively and prove global smoothness of the action.
If , then for some nonzero real . Since and , this forces and hence . The action is free. Two points in the same fibre have representatives for some ; absorb into the real scaling and use . Thus the orbits are exactly the fibres.
Let and . Using these base coordinates, define
Both formulas are invariant under real nonzero scaling, including negative scaling. Their inverses are
Again the sign of the root does not matter. Direct substitution shows they are two-sided inverses. The forward maps are smooth, and local square-root branches prove that the inverses are smooth. Under the right action, each squared phase is multiplied by , so the maps are equivariant. They are therefore genuine principal trivializations of the principal circle bundle on real projective three-space.
On the overlap , we have and
Consequently
When the base point itself, rather than its chart coordinate, is written as , its coordinate remains in the general transition formula. The opposite transition has reciprocal multiplier. The doubled phase is essential to freeness and is not the ordinary Hopf-bundle phase.
A smooth vector field on a smooth manifold is a smooth section of a vector bundle of the tangent bundle projection , so . In a coordinate chart it has the form with smooth component functions .
Suppose a smooth vector bundle isomorphism covering the identity is given. For the standard basis of , put . These are smooth vector fields, and the linear isomorphism on each fibre makes a basis of .
Conversely, given such a global frame of a vector bundle, define
It is smooth, covers the identity and is a linear isomorphism on each fibre. Its inverse is smooth as well: in any coordinate chart, the component columns of the form an invertible smooth matrix , and the fibre coordinates of the inverse are . matrix inversion is smooth on the invertible matrices. Thus the tangent bundle is trivial exactly when a global frame exists, the defining property of a parallelizable manifold.
For a Lie group , write . A left-invariant vector field is a field satisfying
Such a field is determined by , since . Conversely, this formula defines a left-invariant field, by the chain rule and .
It also proves smoothness even if smoothness was not initially assumed. Choose a smooth curve with , . Then
Multiplication is a smooth map on a Lie group, so differentiating its coordinate functions in the second variable yields a smooth function of . This gives smooth components for in every local chart.
Choose a basis of , where , and left translate it. Each is a diffeomorphism, with inverse , so is a linear isomorphism and the translated fields are a basis at every . The explicit parallelization of a Lie group by left translations is
Its inverse sends to . Identifying with gives the required product bundle. The differential facts used are linearity, the chain rule, and smooth dependence of the differential of a smooth map on its base point.
The Frankl-Wilson theorem is a striking example of the polynomial method in combinatorics: an intersection restriction creates a family of linearly independent low-degree polynomials, whose dimension bounds the set family. Let be a prime number, let have elements, and let be a set family such that member sizes modulo avoid while every distinct pair has intersection size in modulo . Its general modular form gives
If all members have the same size and , the uniform refinement gives .
For the proof, work over the finite field and associate to the modular intersection polynomial
At the characteristic vector of a set , this equals zero for and is nonzero for . A linear relation among the evaluation functions therefore has every coefficient zero. The multilinear reduction on the Boolean cube, replacing by for , preserves these evaluations and the degree bound . There are possible square-free monomials, proving the general form.
For uniform members, the low-degree evaluation rank on a uniform layer supplies the sharper dimension bound. To verify this without division modulo , form the integer incidence matrix with rows indexed by subsets of size at most , columns indexed by -subsets , and entries . Over the rational numbers, a row with is times the sum of all size- rows containing . Its matrix rank is at most . Every larger integer minor is consequently zero and remains zero modulo , giving the same bound over . The nonzero diagonal evaluation matrix of the then forces .
The theorem, proved by Frankl and Wilson in 1981, extends the theme of the Ray-Chaudhuri–Wilson theorem from ordinary intersection sizes to residues. Modular restrictions can be weaker than exact intersection restrictions yet still force unexpectedly small families. Here are three consequences from one explicit modular intersection graph.
Take , , and let the vertices be all -subsets of , with an edge exactly when the intersection has size . An independent set avoids the only possible off-diagonal intersection congruent to modulo , so applying the Frankl-Wilson theorem with gives
A clique has one exact intersection size. Apply the uniform theorem modulo a prime larger than , with , to get . Since there are vertices, this gives the explicit asymmetric Ramsey number bound . It illustrates how algebraic constructions produce graphs with simultaneously restricted cliques and independent sets.
For a geometric application, map each vertex to in . Then , so edges have unit Euclidean distance. Every proper colouring of Euclidean space therefore colours this finite graph, giving
The Stirling formula gives the ratio as , where is the binary entropy function in natural-log units. The positive constant proves an exponential chromatic number of Euclidean space lower bound along these dimensions.
Finally, a quadratic embedding converts this same forbidden intersection into a forbidden diameter pair. Set and . The quadratic sign-vector diameter formula follows from the Frobenius inner product:
For distinct members the smallest possible absolute inner product is one, attained exactly when the intersection is . Thus maximum-distance pairs are exactly edges of . The matrices have common diagonal; using their off-diagonal coordinates, multiplied by , realizes them isometrically in dimensions. They are distinct because equal outer products require , and complements have size , not .
Any subset of smaller diameter contains at most points, so a partition into smaller-diameter pieces needs at least pieces. For sufficiently large primes this exceeds , disproving the Borsuk conjecture. This is the mechanism behind the Kahn-Kalai counterexample to the Borsuk conjecture: the number of required pieces grows exponentially in the original set-system parameter while dimension grows quadratically. Their 1993 paper establishes the resulting high-dimensional counterexample.
Let be the monotone Boolean function of the edge indicators asserting that an -vertex graph contains an -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 . Consider upward-closed set families of subsets of of size at most . Impose the Razborov closure rule: if have pairwise intersections contained in , adjoin whenever . 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 by
Closed families form the finite lattice approximation for monotone clique circuits, with meet and join . An input edge is represented by the family of its supersets up to size . The constant predicates have the empty and full families. The assumed approximation theorem says that a size- circuit's output disagreement is covered by at most local gate errors:
We need the Erdős–Rado sunflower lemma: an -uniform set family with more than members contains members with a common pairwise intersection. Its short induction proves the bound. A maximal disjoint subfamily either has members, already the required empty-core delta-system, or its union has at most points and meets every member. Some point then occurs in more than members. Delete it, apply the induction hypothesis, and restore it to the core. Thus an -closed family has at most
inclusion-minimal -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 -subset and the graph having exactly the edges of its clique. Put and suppose . A nonuniversal family has no minimal member of size at most one, so it accepts at most
of positive inputs. Here .
If is in a meet-error set, it contains minimal witnesses . Their union must have size greater than , since otherwise upward closure would put it in . At least one witness therefore has size greater than . The same counting and the union bound give the positive clique error of a truncated lattice meet:
For negative inputs independently assign one of colours to each vertex, joining differently coloured vertices. Every resulting complete multipartite graph is -clique-free. Consider one forcing step adjoining . If its clique is newly accepted, is rainbow while all witnesses are not. Condition on the colours of . The sets 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 most
When this is at most , a step makes a negative error with probability at most . 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 sets can be forced. The negative colouring error of a forced-set closure is therefore
Set and . For sufficiently large , both probability conditions hold and . If the output approximation is nonuniversal, it misses at least half the positive inputs, so the Razborov gate-by-gate approximation lemma forces . If it is universal, it accepts every negative colouring input, forcing . Consequently
Since and grows faster than , both terms imply
for an absolute positive and all sufficiently large . This is superpolynomial in the input bits. The argument concerns AND/OR monotone circuits; it gives no such bound for circuits allowed negation.
Let be the maximum number of positive Euclidean distances from one of the points to the others. It suffices to prove the stronger Székely distinct-distance bound, . Here ; enlarge constants to handle bounded .
First prove the crossing lemma for multigraphs. In an optimal drawing of a loopless multigraph with vertices, edges and maximum parallel multiplicity , crossings of incident edges can be removed by interchanging initial segments, so each remaining crossing involves four distinct vertices. In each parallel class choose one of its edges with probability per edge, selecting none with the remaining probability. Independently keep each vertex with probability . The resulting simple graph has expected edge count , expected vertex count , and expected crossings , where is the original crossing count. Deleting one edge per crossing and using the allowed planar graph edge bound yields
If , take to obtain
The case is the ordinary crossing lemma.
We also need the rich line bound. Given lines, connect consecutive incidence points on each line by straight edges. This simple graph has at least edges, where is the total number of incidences, and at most crossings. The crossing lemma gives , proving the Szemerédi–Trotter theorem here rather than assuming it. For lines containing at least points, , and absorbing the additive term gives
For bounded , counting point pairs gives the same estimate with a larger absolute constant. Grouping rich lines into occupancy ranges and summing the resulting geometric series proves
Now form the circular-arc graph for distinct distances. Around every point draw each positive-distance circle centred there; there are at most such circles. A circle with at least three of the original points contributes one edge between each consecutive pair around it. Discard the circles with at most two points. Since the total number of centre-to-point incidences is , the remaining loopless multigraph has
Its circular-arc drawing has crossings: two distinct circles have at most two intersections, and small perturbations remove tangencies and multiple crossings without changing this order.
The apparent difficulty is unbounded parallel multiplicity. The rich-bisector deletion bound controls it. Every centre supporting an arc between fixed endpoints lies on their perpendicular bisector. Distinct parallel arcs come from distinct centres, since their common endpoints determine the radius once the centre is fixed. Thus multiplicity at least makes that line contain at least of the points. For a line with centres, each of its at most circles has at most two consecutive-point arcs symmetric about that line, one at each end of its diameter along the line. The occupancy sum above therefore bounds the number of high-multiplicity arcs by
If there is nothing to prove. Otherwise and . Choose with a sufficiently large absolute constant . The first deletion term is at most a small fixed fraction of and the second is . A remaining multigraph therefore has edges and multiplicity at most . For large , , so the crossing lemma for multigraphs gives
Rearranging,
The whole distinct-distance set contains those distances from the selected point, proving the requested bound. The circular-arc method and the stronger one-point conclusion are due to Székely.
For disjoint vertex sets , define their edge density of a bipartite graph by . They form a regular pair with parameter if every with , satisfies .
The Szemerédi regularity lemma says that for every and minimum cell count , some have the following property. Every graph on vertices admits
with , equal-sized , and at most unordered irregular pairs. It is enough to consider .
Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and set
with ordered pairs and the adjacency indicator also defining diagonal densities. Then . The refinement variance identity for regularity energy proves refinement cannot decrease :
An irregular pair supplies witness subsets of relative sizes at least whose density differs by more than . Refining along those witnesses raises by more than per orientation, where is the common cell size. If there are more than irregular pairs, the increase is greater than , provided the exceptional set has size at most .
Refine each cell by all its witness subsets; this produces at most atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most vertices become exceptional, and, when , at most new nonexceptional cells occur.
Put and start with so large that . An initial equitable partition has at most exceptional vertices when is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most . The recurrence , iterated at most times, supplies a finite bound ; choose large enough that every intermediate meets the size requirement. More than unsuccessful refinements would raise above one. The process must therefore stop with the required regular pairs. This proves the lemma.
Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding , triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on ; the lemma is a structural tool, not a promise of small practical constants.

There are unlisted articles, also show them or only show them.