You are currently browsing the category archive for the ‘math.CO’ category.

Let , be additive groups (i.e., groups with an abelian addition group law). A map is a homomorphism if one has

for all . A map is an *affine* homomorphism if one has

for all *additive quadruples* in , by which we mean that and . The two notions are closely related; it is easy to verify that is an affine homomorphism if and only if is the sum of a homomorphism and a constant.

Now suppose that also has a translation-invariant metric . A map is said to be a quasimorphism if one has

for all , where denotes a quantity at a bounded distance from the origin. Similarly, is an *affine quasimorphism* if

for all additive quadruples in . Again, one can check that is an affine quasimorphism if and only if it is the sum of a quasimorphism and a constant (with the implied constant of the quasimorphism controlled by the implied constant of the affine quasimorphism). (Since every constant is itself a quasimorphism, it is in fact the case that affine quasimorphisms are quasimorphisms, but now the implied constant in the latter is not controlled by the implied constant of the former.)

“Trivial” examples of quasimorphisms include the sum of a homomorphism and a bounded function. Are there others? In some cases, the answer is no. For instance, suppose we have a quasimorphism . Iterating (2), we see that for any integer and natural number , which we can rewrite as for non-zero . Also, is Lipschitz. Sending , we can verify that is a Cauchy sequence as and thus tends to some limit ; we have for , hence for positive , and then one can use (2) one last time to obtain for all . Thus is the sum of the homomorphism and a bounded sequence.

In general, one can phrase this problem in the language of group cohomology (discussed in this previous post). Call a map a *-cocycle*. A *-cocycle* is a map obeying the identity

for all . Given a -cocycle , one can form its *derivative* by the formula

Such functions are called *-coboundaries*. It is easy to see that the abelian group of -coboundaries is a subgroup of the abelian group of -cocycles. The quotient of these two groups is the first group cohomology of with coefficients in , and is denoted .

If a -cocycle is bounded then its derivative is a bounded -coboundary. The quotient of the group of bounded -cocycles by the derivatives of bounded -cocycles is called the *bounded first group cohomology* of with coefficients in , and is denoted . There is an obvious homomorphism from to , formed by taking a coset of the space of derivatives of bounded -cocycles, and enlarging it to a coset of the space of -coboundaries. By chasing all the definitions, we see that all quasimorphism from to are the sum of a homomorphism and a bounded function if and only if this homomorphism is injective; in fact the quotient of the space of quasimorphisms by the sum of homomorphisms and bounded functions is isomorphic to the kernel of .

In additive combinatorics, one is often working with functions which only have additive structure a fraction of the time, thus for instance (1) or (3) might only hold “ of the time”. This makes it somewhat difficult to directly interpret the situation in terms of group cohomology. However, thanks to tools such as the Balog-Szemerédi-Gowers lemma, one can upgrade this sort of -structure to -structure – at the cost of restricting the domain to a smaller set. Here I record one such instance of this phenomenon, thus giving a tentative link between additive combinatorics and group cohomology. (I thank Yuval Wigderson for suggesting the problem of locating such a link.)

Theorem 1Let , be additive groups with , let be a subset of , let , and let be a function such thatfor additive quadruples in . Then there exists a subset of containing with , a subset of with , and a function such that

for all (thus, the derivative takes values in on ), and such that for each , one has

Presumably the constants and can be improved further, but we have not attempted to optimise these constants. We chose as the domain on which one has a bounded derivative, as one can use the Bogulybov lemma (see e.g, Proposition 4.39 of my book with Van Vu) to find a large Bohr set inside . In applications, the set need not have bounded size, or even bounded doubling; for instance, in the inverse theory over a small finite fields , one would be interested in the situation where is the group of matrices with coefficients in (for some large , and being the subset consisting of those matrices of rank bounded by some bound .

*Proof:* By hypothesis, there are triples such that and

Thus, there is a set with such that for all , one has (6) for pairs with ; in particular, there exists such that (6) holds for values of . Setting , we conclude that for each , one has

Consider the bipartite graph whose vertex sets are two copies of , and and connected by a (directed) edge if and (7) holds. Then this graph has edges. Applying (a slight modification of) the Balog-Szemerédi-Gowers theorem (for instance by modifying the proof of Corollary 5.19 of my book with Van Vu), we can then find a subset of with with the property that for any , there exist triples such that the edges all lie in this bipartite graph. This implies that, for all , there exist septuples obeying the constraints

and for . These constraints imply in particular that

Also observe that

Thus, if and are such that , we see that

for octuples in the hyperplane

By the pigeonhole principle, this implies that for any fixed , there can be at most sets of the form with , that are pairwise disjoint. Using a greedy algorithm, we conclude that there is a set of cardinality , such that each set with , intersects for some , or in other words that

This implies that there exists a subset of with , and an element for each , such that

for all . Note we may assume without loss of generality that and .

By construction of , and permuting labels, we can find 16-tuples such that

and

for . We sum this to obtain

and hence by (8)

where . Since

we see that there are only possible values of . By the pigeonhole principle, we conclude that at most of the sets can be disjoint. Arguing as before, we conclude that there exists a set of cardinality such that

whenever (10) holds.

For any , write arbitrarily as for some (with if , and if ) and then set

Then from (11) we have (4). For we have , and (5) then follows from (9).

I have just uploaded to the arXiv the paper “An inverse theorem for an inequality of Kneser“, submitted to a special issue of the Proceedings of the Steklov Institute of Mathematics in honour of Sergei Konyagin. It concerns an inequality of Kneser discussed previously in this blog, namely that

whenever are compact non-empty subsets of a compact connected additive group with probability Haar measure . (A later result of Kemperman extended this inequality to the nonabelian case.) This inequality is non-trivial in the regime

The connectedness of is essential, otherwise one could form counterexamples involving proper subgroups of of positive measure. In the blog post, I indicated how this inequality (together with a more “robust” strengthening of it) could be deduced from submodularity inequalities such as

which in turn easily follows from the identity and the inclusion , combined with the inclusion-exclusion formula.

In the non-trivial regime (2), equality can be attained in (1), for instance by taking to be the unit circle and to be arcs in that circle (obeying (2)). A bit more generally, if is an arbitrary connected compact abelian group and is a non-trivial character (i.e., a continuous homomorphism), then must be surjective (as has no non-trivial connected subgroups), and one can take and for some arcs in that circle (again choosing the measures of these arcs to obey (2)). The main result of this paper is an inverse theorem that asserts that this is the only way in which equality can occur in (1) (assuming (2)); furthermore, if (1) is close to being satisfied with equality and (2) holds, then must be close (in measure) to an example of the above form . Actually, for technical reasons (and for the applications we have in mind), it is important to establish an inverse theorem not just for (1), but for the more robust version mentioned earlier (in which the sumset is replaced by the partial sumset consisting of “popular” sums).

Roughly speaking, the idea is as follows. Let us informally call a *critical pair* if (2) holds and the inequality (1) (or more precisely, a robust version of this inequality) is almost obeyed with equality. The notion of a critical pair obeys some useful closure properties. Firstly, it is symmetric in , and invariant with respect to translation of either or . Furthermore, from the submodularity inequality (3), one can show that if and are critical pairs (with and positive), then and are also critical pairs. (Note that this is consistent with the claim that critical pairs only occur when come from arcs of a circle.) Similarly, from associativity , one can show that if and are critical pairs, then so are and .

One can combine these closure properties to obtain further ones. For instance, suppose is such that . Then (cheating a little bit), one can show that is also a critical pair, basically because is the union of the , , the are all critical pairs, and the all intersect each other. This argument doesn’t quite work as stated because one has to apply the closure property under union an uncountable number of times, but it turns out that if one works with the robust version of sumsets and uses a random sampling argument to approximate by the union of finitely many of the , then the argument can be made to work.

Using all of these closure properties, it turns out that one can start with an arbitrary critical pair and end up with a small set such that and are also critical pairs for all (say), where is the -fold sumset of . (Intuitively, if are thought of as secretly coming from the pullback of arcs by some character , then should be the pullback of a much shorter arc by the same character.) In particular, exhibits linear growth, in that for all . One can now use standard technology from inverse sumset theory to show first that has a very large Fourier coefficient (and thus is biased with respect to some character ), and secondly that is in fact almost of the form for some arc , from which it is not difficult to conclude similar statements for and and thus finish the proof of the inverse theorem.

In order to make the above argument rigorous, one has to be more precise about what the modifier “almost” means in the definition of a critical pair. I chose to do this in the language of “cheap” nonstandard analysis (aka asymptotic analysis), as discussed in this previous blog post; one could also have used the full-strength version of nonstandard analysis, but this does not seem to convey any substantial advantages. (One can also work in a more traditional “non-asymptotic” framework, but this requires one to keep much more careful account of various small error terms and leads to a messier argument.)

*[Update, Nov 15: Corrected the attribution of the inequality (1) to Kneser instead of Kemperman. Thanks to John Griesmer for pointing out the error.]*

Let be the Liouville function, thus is defined to equal when is the product of an even number of primes, and when is the product of an odd number of primes. The Chowla conjecture asserts that has the statistics of a random sign pattern, in the sense that

for all and all distinct natural numbers , where we use the averaging notation

For , this conjecture is equivalent to the prime number theorem (as discussed in this previous blog post), but the conjecture remains open for any .

In recent years, it has been realised that one can make more progress on this conjecture if one works instead with the logarithmically averaged version

of the conjecture, where we use the logarithmic averaging notation

Using the summation by parts (or telescoping series) identity

it is not difficult to show that the Chowla conjecture (1) for a given implies the logarithmically averaged conjecture (2). However, the converse implication is not at all clear. For instance, for , we have already mentioned that the Chowla conjecture

is equivalent to the prime number theorem; but the logarithmically averaged analogue

is significantly easier to show (a proof with the Liouville function replaced by the closely related Möbius function is given in this previous blog post). And indeed, significantly more is now known for the logarithmically averaged Chowla conjecture; in this paper of mine I had proven (2) for , and in this recent paper with Joni Teravainen, we proved the conjecture for all odd (with a different proof also given here).

In view of this emerging consensus that the logarithmically averaged Chowla conjecture was easier than the ordinary Chowla conjecture, it was thus somewhat of a surprise for me to read a recent paper of Gomilko, Kwietniak, and Lemanczyk who (among other things) established the following statement:

Theorem 1Assume that the logarithmically averaged Chowla conjecture (2) is true for all . Then there exists a sequence going to infinity such that the Chowla conjecture (1) is true for all along that sequence, that is to sayfor all and all distinct .

This implication does not use any special properties of the Liouville function (other than that they are bounded), and in fact proceeds by ergodic theoretic methods, focusing in particular on the ergodic decomposition of invariant measures of a shift into ergodic measures. Ergodic methods have proven remarkably fruitful in understanding these sorts of number theoretic and combinatorial problems, as could already be seen by the ergodic theoretic proof of Szemerédi’s theorem by Furstenberg, and more recently by the work of Frantzikinakis and Host on Sarnak’s conjecture. (My first paper with Teravainen also uses ergodic theory tools.) Indeed, many other results in the subject were first discovered using ergodic theory methods.

On the other hand, many results in this subject that were first proven ergodic theoretically have since been reproven by more combinatorial means; my second paper with Teravainen is an instance of this. As it turns out, one can also prove Theorem 1 by a standard combinatorial (or probabilistic) technique known as the second moment method. In fact, one can prove slightly more:

Theorem 2Let be a natural number. Assume that the logarithmically averaged Chowla conjecture (2) is true for . Then there exists a set of natural numbers of logarithmic density (that is, ) such thatfor any distinct .

It is not difficult to deduce Theorem 1 from Theorem 2 using a diagonalisation argument. Unfortunately, the known cases of the logarithmically averaged Chowla conjecture ( and odd ) are currently insufficient to use Theorem 2 for any purpose other than to reprove what is already known to be true from the prime number theorem. (Indeed, the even cases of Chowla, in either logarithmically averaged or non-logarithmically averaged forms, seem to be far more powerful than the odd cases; see Remark 1.7 of this paper of myself and Teravainen for a related observation in this direction.)

We now sketch the proof of Theorem 2. For any distinct , we take a large number and consider the limiting the second moment

We can expand this as

If all the are distinct, the hypothesis (2) tells us that the inner averages goes to zero as . The remaining averages are , and there are of these averages. We conclude that

By Markov’s inequality (and (3)), we conclude that for any fixed , there exists a set of upper logarithmic density at least , thus

such that

By deleting at most finitely many elements, we may assume that consists only of elements of size at least (say).

For any , if we let be the union of for , then has logarithmic density . By a diagonalisation argument (using the fact that the set of tuples is countable), we can then find a set of natural numbers of logarithmic density , such that for every , every sufficiently large element of lies in . Thus for every sufficiently large in , one has

for some with . By Cauchy-Schwarz, this implies that

interchanging the sums and using and , this implies that

We conclude on taking to infinity that

as required.

Szemerédi’s theorem asserts that all subsets of the natural numbers of positive density contain arbitrarily long arithmetic progressions. *Roth’s theorem* is the special case when one considers arithmetic progressions of length three. Both theorems have many important proofs using tools from additive combinatorics, (higher order) Fourier analysis, (hyper) graph regularity theory, and ergodic theory. However, the original proof by Endre Szemerédi, while extremely intricate, was purely combinatorial (and in particular “elementary”) and almost entirely self-contained, except for an invocation of the van der Waerden theorem. It is also notable for introducing a prototype of what is now known as the Szemerédi regularity lemma.

Back in 2005, I rewrote Szemerédi’s original proof in order to understand it better, however my rewrite ended up being about the same length as the original argument and was probably only usable to myself. In 2012, after Szemerédi was awarded the Abel prize, I revisited this argument with the intention to try to write up a more readable version of the proof, but ended up just presenting some ingredients of the argument in a blog post, rather than try to rewrite the whole thing. In that post, I suspected that the cleanest way to write up the argument would be through the language of nonstandard analysis (perhaps in an iterated hyperextension that could handle various hierarchies of infinitesimals), but was unable to actually achieve any substantial simplifications by passing to the nonstandard world.

A few weeks ago, I participated in a week-long workshop at the American Institute of Mathematics on “Nonstandard methods in combinatorial number theory”, and spent some time in a working group with Shabnam Akhtari, Irfam Alam, Renling Jin, Steven Leth, Karl Mahlburg, Paul Potgieter, and Henry Towsner to try to obtain a manageable nonstandard version of Szemerédi’s original proof. We didn’t end up being able to do so – in fact there are now signs that perhaps nonstandard analysis is not the optimal framework in which to place this argument – but we did at least clarify the existing standard argument, to the point that I was able to go back to my original rewrite of the proof and present it in a more civilised form, which I am now uploading here as an unpublished preprint. There are now a number of simplifications to the proof. Firstly, one no longer needs the full strength of the regularity lemma; only the simpler “weak” regularity lemma of Frieze and Kannan is required. Secondly, the proof has been “factored” into a number of stand-alone propositions of independent interest, in particular involving just (families of) one-dimensional arithmetic progressions rather than the complicated-looking multidimensional arithmetic progressions that occur so frequently in the original argument of Szemerédi. Finally, the delicate manipulations of densities and epsilons via double counting arguments in Szemerédi’s original paper have been abstracted into a certain key property of families of arithmetic progressions that I call the “double counting property”.

The factoring mentioned above is particularly simple in the case of proving Roth’s theorem, which is now presented separately in the above writeup. Roth’s theorem seeks to locate a length three progression in which all three elements lie in a single set. This will be deduced from an easier variant of the theorem in which one locates (a family of) length three progressions in which just the first two elements of the progression lie in a good set (and some other properties of the family are also required). This is in turn derived from an even easier variant in which now just the first element of the progression is required to be in the good set.

More specifically, Roth’s theorem is now deduced from

Theorem 1.5. Let be a natural number, and let be a set of integers of upper density at least . Then, whenever is partitioned into finitely many colour classes, there exists a colour class and a family of 3-term arithmetic progressions with the following properties:

- For each , and lie in .
- For each , lie in .
- The for are in arithmetic progression.

The situation in this theorem is depicted by the following diagram, in which elements of are in blue and elements of are in grey:

Theorem 1.5 is deduced in turn from the following easier variant:

Theorem 1.6. Let be a natural number, and let be a set of integers of upper density at least . Then, whenever is partitioned into finitely many colour classes, there exists a colour class and a family of 3-term arithmetic progressions with the following properties:

- For each , lie in .
- For each , and lie in .
- The for are in arithmetic progression.

The situation here is described by the figure below.

Theorem 1.6 is easy to prove. To derive Theorem 1.5 from Theorem 1.6, or to derive Roth’s theorem from Theorem 1.5, one uses double counting arguments, van der Waerden’s theorem, and the weak regularity lemma, largely as described in this previous blog post; see the writeup for the full details. (I would be interested in seeing a shorter proof of Theorem 1.5 though that did not go through these arguments, and did not use the more powerful theorems of Roth or Szemerédi.)

Fix a non-negative integer . Define an (weak) integer partition of length to be a tuple of non-increasing non-negative integers . (Here our partitions are “weak” in the sense that we allow some parts of the partition to be zero. Henceforth we will omit the modifier “weak”, as we will not need to consider the more usual notion of “strong” partitions.) To each such partition , one can associate a Young diagram consisting of left-justified rows of boxes, with the row containing boxes. A semi-standard Young tableau (or *Young tableau* for short) of shape is a filling of these boxes by integers in that is weakly increasing along rows (moving rightwards) and strictly increasing along columns (moving downwards). The collection of such tableaux will be denoted . The *weight* of a tableau is the tuple , where is the number of occurrences of the integer in the tableau. For instance, if and , an example of a Young tableau of shape would be

The weight here would be .

To each partition one can associate the Schur polynomial on variables , which we will define as

using the multinomial convention

Thus for instance the Young tableau given above would contribute a term to the Schur polynomial . In the case of partitions of the form , the Schur polynomial is just the complete homogeneous symmetric polynomial of degree on variables:

thus for instance

Schur polyomials are ubiquitous in the algebraic combinatorics of “type objects” such as the symmetric group , the general linear group , or the unitary group . For instance, one can view as the character of an irreducible polynomial representation of associated with the partition . However, we will not focus on these interpretations of Schur polynomials in this post.

This definition of Schur polynomials allows for a way to describe the polynomials recursively. If and is a Young tableau of shape , taking values in , one can form a sub-tableau of some shape by removing all the appearances of (which, among other things, necessarily deletes the row). For instance, with as in the previous example, the sub-tableau would be

and the reduced partition in this case is . As Young tableaux are required to be strictly increasing down columns, we can see that the reduced partition must *intersperse* the original partition in the sense that

for all ; we denote this interspersion relation as (though we caution that this is *not* intended to be a partial ordering). In the converse direction, if and is a Young tableau with shape with entries in , one can form a Young tableau with shape and entries in by appending to an entry of in all the boxes that appear in the shape but not the shape. This one-to-one correspondence leads to the recursion

where , , and the size of a partition is defined as .

One can use this recursion (2) to prove some further standard identities for Schur polynomials, such as the determinant identity

for , where denotes the Vandermonde determinant

with the convention that if is negative. Thus for instance

We review the (standard) derivation of these identities via (2) below the fold. Among other things, these identities show that the Schur polynomials are symmetric, which is not immediately obvious from their definition.

One can also iterate (2) to write

where the sum is over all tuples , where each is a partition of length that intersperses the next partition , with set equal to . We will call such a tuple an *integral Gelfand-Tsetlin pattern* based at .

One can generalise (6) by introducing the skew Schur functions

for , whenever is a partition of length and a partition of length for some , thus the Schur polynomial is also the skew Schur polynomial with . (One could relabel the variables here to be something like instead, but this labeling seems slightly more natural, particularly in view of identities such as (8) below.)

By construction, we have the decomposition

whenever , and are partitions of lengths respectively. This gives another recursive way to understand Schur polynomials and skew Schur polynomials. For instance, one can use it to establish the generalised Jacobi-Trudi identity

with the convention that for larger than the length of ; we do this below the fold.

The Schur polynomials (and skew Schur polynomials) are “discretised” (or “quantised”) in the sense that their parameters are required to be integer-valued, and their definition similarly involves summation over a discrete set. It turns out that there are “continuous” (or “classical”) analogues of these functions, in which the parameters now take real values rather than integers, and are defined via integration rather than summation. One can view these continuous analogues as a “semiclassical limit” of their discrete counterparts, in a manner that can be made precise using the machinery of geometric quantisation, but we will not do so here.

The continuous analogues can be defined as follows. Define a *real partition* of length to be a tuple where are now real numbers. We can define the relation of interspersion between a length real partition and a length real partition precisely as before, by requiring that the inequalities (1) hold for all . We can then define the continuous Schur functions for recursively by defining

for and of length , where and the integral is with respect to -dimensional Lebesgue measure, and as before. Thus for instance

and

More generally, we can define the continuous skew Schur functions for of length , of length , and recursively by defining

and

for . Thus for instance

and

By expanding out the recursion, one obtains the analogue

of (6), and more generally one has

We will call the tuples in the first integral *real Gelfand-Tsetlin patterns* based at . The analogue of (8) is then

where the integral is over all real partitions of length , with Lebesgue measure.

By approximating various integrals by their Riemann sums, one can relate the continuous Schur functions to their discrete counterparts by the limiting formula

as for any length real partition and any , where

and

More generally, one has

as for any length real partition , any length real partition with , and any .

As a consequence of these limiting formulae, one expects all of the discrete identities above to have continuous counterparts. This is indeed the case; below the fold we shall prove the discrete and continuous identities in parallel. These are not new results by any means, but I was not able to locate a good place in the literature where they are explicitly written down, so I thought I would try to do so here (primarily for my own internal reference, but perhaps the calculations will be worthwhile to some others also).

Ben Green and I have (finally!) uploaded to the arXiv our paper “New bounds for Szemerédi’s theorem, III: A polylogarithmic bound for “, submitted to Mathematika. This is the sequel to two previous papers (and an erratum to the former paper), concerning quantitative versions of Szemerédi’s theorem in the case of length four progressions. This sequel has been delayed for over a decade for a number of reasons, but we have finally managed to write the arguments up to our satisfaction and submit it (to a special issue of Mathematika honouring the work of Klaus Roth).

For any natural number , define to be the largest cardinality of a subset of which does not contain any non-trivial arithmetic progressions of length four (where “non-trivial” means that is non-zero). Trivially we have . In 1969, Szemerédi showed that . However, the decay rate that could be theoretically extracted from this argument (and from several subsequent proofs of this bound, including one by Roth) were quite poor. The first significant quantitative bound on this quantity was by Gowers, who showed that for some absolute constant . In the second paper in the above-mentioned series, we managed to improve this bound to . In this paper, we improve the bound further to , which seems to be the limit of the methods. (We remark that if we could take to be larger than one, this would imply the length four case of a well known conjecture of Erdös that any set of natural numbers whose sum of reciprocals diverges would contain arbitrarily long arithmetic progressions. Thanks to the work of Sanders and of Bloom, the corresponding case of the conjecture for length three conjectures is nearly settled, as it is known that for the analogous bound on one can take any less than one.)

Most of the previous work on bounding relied in some form or another on the *density increment argument* introduced by Roth back in 1953; roughly speaking, the idea is to show that if a dense subset of fails to contain arithmetic progressions of length four, one seeks to then locate a long subprogression of in which has increased density. This was the basic method for instance underlying our previous bound , as well as a finite field analogue of the bound ; however we encountered significant technical difficulties for several years in extending this argument to obtain the result of the current paper. Our method is instead based on “energy increment arguments”, and more specifically on establishing quantitative version of a Khintchine-type recurrence theorem, similar to the qualitative recurrence theorems established (in the ergodic theory context) by Bergelson-Host-Kra, and (in the current combinatorial context) by Ben Green and myself.

One way to phrase the latter recurrence theorem is as follows. Suppose that has density . Then one would expect a “randomly” selected arithmetic progression in (using the convention that random variables will be in boldface) to be contained in with probability about . This is not true in general, however it was shown by Ben and myself that for any , there was a set of shifts of cardinality , such that for any such one had

if was chosen uniformly at random from . This easily implies that , but does not give a particularly good bound on the decay rate, because the implied constant in the cardinality lower bound is quite poor (in fact of tower-exponential type, due to the use of regularity lemmas!), and so one has to take to be extremely large compared to to avoid the possibility that the set of shifts in the above theorem consists only of the trivial shift .

We do not know how to improve the lower bound on the set of shifts to the point where it can give bounds that are competitive with those in this paper. However, we can obtain better quantitative results if we permit ourselves to *couple* together the two parameters and of the length four progression. Namely, with , , as above, we are able to show that there exist random variables , not necessarily independent, such that

and such that we have the non-degeneracy bound

This then easily implies the main theorem.

The energy increment method is then deployed to locate a good pair of random variables that will obey the above bounds. One can get some intuition on how to proceed here by considering some model cases. Firstly one can consider a “globally quadratically structured” case in which the indicator function “behaves like” a globally quadratic function such as , for some irrational and some smooth periodic function of mean . If one then takes to be uniformly distributed in and respectively for some small , with no coupling between the two variables, then the left-hand side of (1) is approximately of the form

where the integral is with respect to the probability Haar measure, and the constraint ultimately arises from the algebraic constraint

However, an application of the Cauchy-Schwarz inequality and Fubini’s theorem shows that the integral in (2) is at least , which (morally at least) gives (1) in this case.

Due to the nature of the energy increment argument, it also becomes necessary to consider “locally quadratically structured” cases, in which is partitioned into some number of structured pieces (think of these as arithmetic progressions, or as “Bohr sets), and on each piece , behaves like a locally quadratic function such as , where now varies with , and the mean of will be approximately on the average after averaging in (weighted by the size of the pieces ). Now one should select and in the following coupled manner: first one chooses uniformly from , then one defines to be the label such that , and then selects uniformly from a set which is related to in much the same way that is related to . If one does this correctly, the analogue of (2) becomes

and one can again use Cauchy-Schwarz and Fubini’s theorem to conclude.

The general case proceeds, very roughly, by an iterative argument. At each stage of the iteration, one has some sort of quadratic model of which involves a decomposition of into structured pieces , and a quadratic approximation to on each piece. If this approximation is accurate enough (or more precisely, if a certain (averaged) local Gowers uniformity norm of the error is small enough) to model the count in (1) (for random variables determined by the above partition of into pieces ), and if the frequencies (such as ) involved in the quadratic approximation are “high rank” or “linearly independent over the rationals” in a suitably quantitative sense, then some version of the above arguments can be made to work. If there are some unwanted linear dependencies in the frequencies, we can do some linear algebra to eliminate one of the frequencies (using some geometry of numbers to keep the quantitative bounds under control) and continue the iteration. If instead the approximation is too inaccurate, then the error will be large in a certain averaged local Gowers uniformity norm . A significant fraction of the paper is then devoted to establishing a quantitative *inverse theorem* for that norm that concludes (with good bounds) that the error must then locally correlate with locally quadratic phases, which can be used to refine the quadratic approximation to in a manner that significantly increases its “energy” (basically an norm). Such energy increments cannot continue indefinitely, and when they terminate we obtain the desired claim.

There are existing inverse theorems for type norms in the literature, going back to the pioneering work of Gowers mentioned previously, and relying on arithmetic combinatorics tools such as Freiman’s theorem and the Balog-Szemerédi-Gowers lemma, which are good for analysing the “-structured homomorphisms” that arise in Gowers’ argument. However, when we applied these methods to the local Gowers norms we obtained inferior quantitative results that were not strong enough for our application. Instead, we use arguments from a different paper of Gowers in which he tackled Szemerédi’s theorem for arbitrary length progressions. This method produces “-structured homomorphisms” associated to any function with large Gowers uniformity norm; however the catch is that such homomorphisms are initially supported only on a sparse unstructured set, rather than a structured set such as a Bohr set. To proceed further, one first has to locate inside the sparse unstructured set a sparse *pseudorandom* subset of a Bohr set, and then use “error-correction” type methods (such as “majority-vote” based algorithms) to locally upgrade this -structured homomorphism on pseudorandom subsets of Bohr sets to a -structured homomorphism on the entirety of a Bohr set. It is then possible to use some “approximate cohomology” tools to “integrate” these homomorphisms (and discern a key “local symmetry” property of these homomorphisms) to locate the desired local quadratic structure (in much the same fashion that a -form on that varies linearly with the coordinates can be integrated to be the derivative of a quadratic function if we know that the -form is closed). These portions of the paper are unfortunately rather technical, but broadly follow the methods already used in previous literature.

How many groups of order four are there? Technically, there are an enormous number, so much so, in fact, that the class of groups of order four is not even a set, but merely a proper class. This is because *any* four objects can be turned into a group by designating one of the four objects, say , to be the group identity, and imposing a suitable multiplication table (and inversion law) on the four elements in a manner that obeys the usual group axioms. Since all sets are themselves objects, the class of four-element groups is thus at least as large as the class of all sets, which by Russell’s paradox is known not to itself be a set (assuming the usual ZFC axioms of set theory).

A much better question is to ask how many groups of order four there are *up to isomorphism*, counting each isomorphism class of groups exactly once. Now, as one learns in undergraduate group theory classes, the answer is just “two”: the cyclic group and the Klein four-group .

More generally, given a class of objects and some equivalence relation on (which one should interpret as describing the property of two objects in being “isomorphic”), one can consider the number of objects in “up to isomorphism”, which is simply the cardinality of the collection of equivalence classes of . In the case where is finite, one can express this cardinality by the formula

thus one counts elements in , weighted by the reciprocal of the number of objects they are isomorphic to.

Example 1Let be the five-element set of integers between and . Let us say that two elements of are isomorphic if they have the same magnitude: . Then the quotient space consists of just three equivalence classes: , , and . Thus there are three objects in up to isomorphism, and the identity (1) is then justThus, to count elements in up to equivalence, the elements are given a weight of because they are each isomorphic to two elements in , while the element is given a weight of because it is isomorphic to just one element in (namely, itself).

Given a finite probability set , there is also a natural probability distribution on , namely the *uniform distribution*, according to which a random variable is set equal to any given element of with probability :

Given a notion of isomorphism on , one can then define the random equivalence class that the random element belongs to. But if the isomorphism classes are unequal in size, we now encounter a biasing effect: even if was drawn uniformly from , the equivalence class need not be uniformly distributed in . For instance, in the above example, if was drawn uniformly from , then the equivalence class will not be uniformly distributed in the three-element space , because it has a probability of being equal to the class or to the class , and only a probability of being equal to the class .

However, it is possible to remove this bias by changing the weighting in (1), and thus changing the notion of what cardinality means. To do this, we generalise the previous situation. Instead of considering sets with an equivalence relation to capture the notion of isomorphism, we instead consider groupoids, which are sets in which there are allowed to be *multiple* isomorphisms between elements in (and in particular, there are allowed to be multiple *automorphisms* from an element to itself). More precisely:

Definition 2A groupoid is a set (or proper class) , together with a (possibly empty) collection of “isomorphisms” between any pair of elements of , and a composition map from isomorphisms , to isomorphisms in for every , obeying the following group-like axioms:

- (Identity) For every , there is an identity isomorphism , such that for all and .
- (Associativity) If , , and for some , then .
- (Inverse) If for some , then there exists an inverse isomorphism such that and .
We say that two elements of a groupoid are

isomorphic, and write , if there is at least one isomorphism from to .

Example 3Any category gives a groupoid by taking to be the set (or class) of objects, and to be the collection of invertible morphisms from to . For instance, in the category of sets, would be the collection of bijections from to ; in the category of linear vector spaces over some given base field , would be the collection of invertible linear transformations from to ; and so forth.

Every set equipped with an equivalence relation can be turned into a groupoid by assigning precisely one isomorphism from to for any pair with , and no isomorphisms from to when , with the groupoid operations of identity, composition, and inverse defined in the only way possible consistent with the axioms. We will call this the *simply connected groupoid* associated with this equivalence relation. For instance, with as above, if we turn into a simply connected groupoid, there will be precisely one isomorphism from to , and also precisely one isomorphism from to , but no isomorphisms from to , , or .

However, one can also form multiply-connected groupoids in which there can be multiple isomorphisms from one element of to another. For instance, one can view as a space that is acted on by multiplication by the two-element group . This gives rise to two types of isomorphisms, an identity isomorphism from to for each , and a negation isomorphism from to for each ; in particular, there are *two* automorphisms of (i.e., isomorphisms from to itself), namely and , whereas the other four elements of only have a single automorphism (the identity isomorphism). One defines composition, identity, and inverse in this groupoid in the obvious fashion (using the group law of the two-element group ); for instance, we have .

For a finite multiply-connected groupoid, it turns out that the natural notion of “cardinality” (or as I prefer to call it, “cardinality up to isomorphism”) is given by the variant

of (1). That is to say, in the multiply connected case, the denominator is no longer the number of objects isomorphic to , but rather the number of *isomorphisms* from to other objects . Grouping together all summands coming from a single equivalence class in , we can also write this expression as

where is the automorphism group of , that is to say the group of isomorphisms from to itself. (Note that if belong to the same equivalence class , then the two groups and will be isomorphic and thus have the same cardinality, and so the above expression is well-defined.

For instance, if we take to be the simply connected groupoid on , then the number of elements of up to isomorphism is

exactly as before. If however we take the multiply connected groupoid on , in which has two automorphisms, the number of elements of up to isomorphism is now the smaller quantity

the equivalence class is now counted with weight rather than due to the two automorphisms on . Geometrically, one can think of this groupoid as being formed by taking the five-element set , and “folding it in half” around the fixed point , giving rise to two “full” quotient points and one “half” point . More generally, given a finite group acting on a finite set , and forming the associated multiply connected groupoid, the cardinality up to isomorphism of this groupoid will be , since each element of will have isomorphisms on it (whether they be to the same element , or to other elements of ).

The definition (2) can also make sense for some infinite groupoids; to my knowledge this was first explicitly done in this paper of Baez and Dolan. Consider for instance the category of finite sets, with isomorphisms given by bijections as in Example 3. Every finite set is isomorphic to for some natural number , so the equivalence classes of may be indexed by the natural numbers. The automorphism group of has order , so the cardinality of up to isomorphism is

(This fact is sometimes loosely stated as “the number of finite sets is “, but I view this statement as somewhat misleading if the qualifier “up to isomorphism” is not added.) Similarly, when one allows for multiple isomorphisms from a group to itself, the number of groups of order four up to isomorphism is now

because the cyclic group has two automorphisms, whereas the Klein four-group has six.

In the case that the cardinality of a groupoid up to isomorphism is finite and non-empty, one can now define the notion of a random isomorphism class in drawn “uniformly up to isomorphism”, by requiring the probability of attaining any given isomorphism class to be

thus the probability of being isomorphic to a given element will be inversely proportional to the number of automorphisms that has. For instance, if we take to be the set with the simply connected groupoid, will be drawn uniformly from the three available equivalence classes , with a probability of attaining each; but if instead one uses the multiply connected groupoid coming from the action of , and draws uniformly up to isomorphism, then and will now be selected with probability each, and will be selected with probability . Thus this distribution has accounted for the bias mentioned previously: if a finite group acts on a finite space , and is drawn uniformly from , then now still be drawn uniformly up to isomorphism from , if we use the multiply connected groupoid coming from the action, rather than the simply connected groupoid coming from just the -orbit structure on .

Using the groupoid of finite sets, we see that a finite set chosen uniformly up to isomorphism will have a cardinality that is distributed according to the Poisson distribution of parameter , that is to say it will be of cardinality with probability .

One important source of groupoids are the fundamental groupoids of a manifold (one can also consider more general topological spaces than manifolds, but for simplicity we will restrict this discussion to the manifold case), in which the underlying space is simply , and the isomorphisms from to are the equivalence classes of paths from to up to homotopy; in particular, the automorphism group of any given point is just the fundamental group of at that base point. The equivalence class of a point in is then the connected component of in . The cardinality up to isomorphism of the fundamental groupoid is then

where is the collection of connected components of , and is the order of the fundamental group of . Thus, simply connected components of count for a full unit of cardinality, whereas multiply connected components (which can be viewed as quotients of their simply connected cover by their fundamental group) will count for a fractional unit of cardinality, inversely to the order of their fundamental group.

This notion of cardinality up to isomorphism of a groupoid behaves well with respect to various basic notions. For instance, suppose one has an -fold covering map of one finite groupoid by another . This means that is a functor that is surjective, with all preimages of cardinality , with the property that given any pair in the base space and any in the preimage of , every isomorphism has a unique lift from the given initial point (and some in the preimage of ). Then one can check that the cardinality up to isomorphism of is times the cardinality up to isomorphism of , which fits well with the geometric picture of as the -fold cover of . (For instance, if one covers a manifold with finite fundamental group by its universal cover, this is a -fold cover, the base has cardinality up to isomorphism, and the universal cover has cardinality one up to isomorphism.) Related to this, if one draws an equivalence class of uniformly up to isomorphism, then will be an equivalence class of drawn uniformly up to isomorphism also.

Indeed, one can show that this notion of cardinality up to isomorphism for groupoids is uniquely determined by a small number of axioms such as these (similar to the axioms that determine Euler characteristic); see this blog post of Qiaochu Yuan for details.

The probability distributions on isomorphism classes described by the above recipe seem to arise naturally in many applications. For instance, if one draws a profinite abelian group up to isomorphism at random in this fashion (so that each isomorphism class of a profinite abelian group occurs with probability inversely proportional to the number of automorphisms of this group), then the resulting distribution is known as the *Cohen-Lenstra distribution*, and seems to emerge as the natural asymptotic distribution of many randomly generated profinite abelian groups in number theory and combinatorics, such as the class groups of random quadratic fields; see this previous blog post for more discussion. For a simple combinatorial example, the set of fixed points of a random permutation on elements will have a cardinality that converges in distribution to the Poisson distribution of rate (as discussed in this previous post), thus we see that the fixed points of a large random permutation asymptotically are distributed uniformly up to isomorphism. I’ve been told that this notion of cardinality up to isomorphism is also particularly compatible with stacks (which are a good framework to describe such objects as moduli spaces of algebraic varieties up to isomorphism), though I am not sufficiently acquainted with this theory to say much more than this.

Daniel Kane and I have just uploaded to the arXiv our paper “A bound on partitioning clusters“, submitted to the Electronic Journal of Combinatorics. In this short and elementary paper, we consider a question that arose from biomathematical applications: given a finite family of sets (or “clusters”), how many ways can there be of partitioning a set in this family as the disjoint union of two other sets in this family? That is to say, what is the best upper bound one can place on the quantity

in terms of the cardinality of ? A trivial upper bound would be , since this is the number of possible pairs , and clearly determine . In our paper, we establish the improved bound

where is the somewhat strange exponent

so that . Furthermore, this exponent is best possible!

Actually, the latter claim is quite easy to show: one takes to be all the subsets of of cardinality either or , for a multiple of , and the claim follows readily from Stirling’s formula. So it is perhaps the former claim that is more interesting (since many combinatorial proof techniques, such as those based on inequalities such as the Cauchy-Schwarz inequality, tend to produce exponents that are rational or at least algebraic). We follow the common, though unintuitive, trick of generalising a problem to make it simpler. Firstly, one generalises the bound to the “trilinear” bound

for arbitrary finite collections of sets. One can place all the sets in inside a single finite set such as , and then by replacing every set in by its complement in , one can phrase the inequality in the equivalent form

for arbitrary collections of subsets of . We generalise further by turning sets into functions, replacing the estimate with the slightly stronger convolution estimate

for arbitrary functions on the Hamming cube , where the convolution is on the integer lattice rather than on the finite field vector space . The advantage of working in this general setting is that it becomes very easy to apply induction on the dimension ; indeed, to prove this estimate for arbitrary it suffices to do so for . This reduces matters to establishing the elementary inequality

for all , which can be done by a combination of undergraduate multivariable calculus and a little bit of numerical computation. (The left-hand side turns out to have local maxima at , with the latter being the cause of the numerology (1).)

The same sort of argument also gives an energy bound

for any subset of the Hamming cube, where

is the additive energy of . The example shows that the exponent cannot be improved.

I’ve just uploaded to the arXiv my paper “Some remarks on the lonely runner conjecture“, submitted to Contributions to discrete mathematics. I had blogged about the lonely runner conjecture in this previous blog post, and I returned to the problem recently to see if I could obtain anything further. The results obtained were more modest than I had hoped, but they did at least seem to indicate a potential strategy to make further progress on the problem, and also highlight some of the difficulties of the problem.

One can rephrase the lonely runner conjecture as the following covering problem. Given any integer “velocity” and radius , define the *Bohr set* to be the subset of the unit circle given by the formula

where denotes the distance of to the nearest integer. Thus, for positive, is simply the union of the intervals for , projected onto the unit circle ; in the language of the usual formulation of the lonely runner conjecture, represents those times in which a runner moving at speed returns to within of his or her starting position. For any non-zero integers , let be the smallest radius such that the Bohr sets cover the unit circle:

Then define to be the smallest value of , as ranges over tuples of distinct non-zero integers. The Dirichlet approximation theorem quickly gives that

and hence

for any . The lonely runner conjecture is equivalent to the assertion that this bound is in fact optimal:

Conjecture 1 (Lonely runner conjecture)For any , one has .

This conjecture is currently known for (see this paper of Barajas and Serra), but remains open for higher .

It is natural to try to attack the problem by establishing lower bounds on the quantity . We have the following “trivial” bound, that gets within a factor of two of the conjecture:

Proposition 2 (Trivial bound)For any , one has .

*Proof:* It is not difficult to see that for any non-zero velocity and any , the Bohr set has Lebesgue measure . In particular, by the union bound

we see that the covering (1) is only possible if , giving the claim.

So, in some sense, all the difficulty is coming from the need to improve upon the trivial union bound (2) by a factor of two.

Despite the crudeness of the union bound (2), it has proven surprisingly hard to make substantial improvements on the trivial bound . In 1994, Chen obtained the slight improvement

which was improved a little by Chen and Cusick in 1999 to

when was prime. In a recent paper of Perarnau and Serra, the bound

was obtained for arbitrary . These bounds only improve upon the trivial bound by a multiplicative factor of . Heuristically, one reason for this is as follows. The union bound (2) would of course be sharp if the Bohr sets were all disjoint. Strictly speaking, such disjointness is not possible, because all the Bohr sets have to contain the origin as an interior point. However, it is possible to come up with a large number of Bohr sets which are *almost* disjoint. For instance, suppose that we had velocities that were all prime numbers between and , and that was equal to (and in particular was between and . Then each set can be split into a “kernel” interval , together with the “petal” intervals . Roughly speaking, as the prime varies, the kernel interval stays more or less fixed, but the petal intervals range over disjoint sets, and from this it is not difficult to show that

so that the union bound is within a multiplicative factor of of the truth in this case.

This does not imply that is within a multiplicative factor of of , though, because there are not enough primes between and to assign to distinct velocities; indeed, by the prime number theorem, there are only about such velocities that could be assigned to a prime. So, while the union bound could be close to tight for up to Bohr sets, the above counterexamples don’t exclude improvements to the union bound for larger collections of Bohr sets. Following this train of thought, I was able to obtain a logarithmic improvement to previous lower bounds:

Theorem 3For sufficiently large , one has for some absolute constant .

The factors of in the denominator are for technical reasons and might perhaps be removable by a more careful argument. However it seems difficult to adapt the methods to improve the in the numerator, basically because of the obstruction provided by the near-counterexample discussed above.

Roughly speaking, the idea of the proof of this theorem is as follows. If we have the covering (1) for very close to , then the multiplicity function will then be mostly equal to , but occasionally be larger than . On the other hand, one can compute that the norm of this multiplicity function is significantly larger than (in fact it is at least ). Because of this, the norm must be very large, which means that the triple intersections must be quite large for many triples . Using some basic Fourier analysis and additive combinatorics, one can deduce from this that the velocities must have a large structured component, in the sense that there exists an arithmetic progression of length that contains of these velocities. For simplicity let us take the arithmetic progression to be , thus of the velocities lie in . In particular, from the prime number theorem, most of these velocities will not be prime, and will in fact likely have a “medium-sized” prime factor (in the precise form of the argument, “medium-sized” is defined to be “between and “). Using these medium-sized prime factors, one can show that many of the will have quite a large overlap with many of the other , and this can be used after some elementary arguments to obtain a more noticeable improvement on the union bound (2) than was obtained previously.

A modification of the above argument also allows for the improved estimate

if one knows that *all* of the velocities are of size .

In my previous blog post, I showed that in order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that all of the velocities are of size ; I reproduce this argument (slightly cleaned up for publication) in the current preprint. There is unfortunately a huge gap between and , so the above bound (3) does not immediately give any new bounds for . However, one could perhaps try to start attacking the lonely runner conjecture by increasing the range for which one has good results, and by decreasing the range that one can reduce to. For instance, in the current preprint I give an elementary argument (using a certain amount of case-checking) that shows that the lonely runner bound

holds if all the velocities are assumed to lie between and . This upper threshold of is only a tiny improvement over the trivial threshold of , but it seems to be an interesting sub-problem of the lonely runner conjecture to increase this threshold further. One key target would be to get up to , as there are actually a number of -tuples in this range for which (4) holds with equality. The Dirichlet approximation theorem of course gives the tuple , but there is also the double of this tuple, and furthermore there is an additional construction of Goddyn and Wong that gives some further examples such as , or more generally one can start with the standard tuple and accelerate one of the velocities to ; this turns out to work as long as shares a common factor with every integer between and . There are a few more examples of this type in the paper of Goddyn and Wong, but all of them can be placed in an arithmetic progression of length at most, so if one were very optimistic, one could perhaps envision a strategy in which the upper bound of mentioned earlier was reduced all the way to something like , and then a separate argument deployed to treat this remaining case, perhaps isolating the constructions of Goddyn and Wong (and possible variants thereof) as the only extreme cases.

I’ve just uploaded to the arXiv my paper “An integration approach to the Toeplitz square peg problem“, submitted to Forum of Mathematics, Sigma. This paper resulted from my attempts recently to solve the Toeplitz square peg problem (also known as the inscribed square problem):

Conjecture 1 (Toeplitz square peg problem)Let be a simple closed curve in the plane. Is it necessarily the case that contains four vertices of a square?

See this recent survey of Matschke in the Notices of the AMS for the latest results on this problem.

The route I took to the results in this paper was somewhat convoluted. I was motivated to look at this problem after lecturing recently on the Jordan curve theorem in my class. The problem is superficially similar to the Jordan curve theorem in that the result is known (and rather easy to prove) if is sufficiently regular (e.g. if it is a polygonal path), but seems to be significantly more difficult when the curve is merely assumed to be continuous. Roughly speaking, all the known positive results on the problem have proceeded using (in some form or another) tools from homology: note for instance that one can view the conjecture as asking whether the four-dimensional subset of the eight-dimensional space necessarily intersects the four-dimensional space consisting of the quadruples traversing a square in (say) anti-clockwise order; this space is a four-dimensional linear subspace of , with a two-dimensional subspace of “degenerate” squares removed. If one ignores this degenerate subspace, one can use intersection theory to conclude (under reasonable “transversality” hypotheses) that intersects an odd number of times (up to the cyclic symmetries of the square), which is basically how Conjecture 1 is proven in the regular case. Unfortunately, if one then takes a limit and considers what happens when is just a continuous curve, the odd number of squares created by these homological arguments could conceivably all degenerate to points, thus blocking one from proving the conjecture in the general case.

Inspired by my previous work on finite time blowup for various PDEs, I first tried looking for a counterexample in the category of (locally) self-similar curves that are smooth (or piecewise linear) away from a single origin where it can oscillate infinitely often; this is basically the smoothest type of curve that was not already covered by previous results. By a rescaling and compactness argument, it is not difficult to see that such a counterexample would exist if there was a counterexample to the following periodic version of the conjecture:

Conjecture 2 (Periodic square peg problem)Let be two disjoint simple closed piecewise linear curves in the cylinder which have a winding number of one, that is to say they are homologous to the loop from to . Then the union of and contains the four vertices of a square.

In contrast to Conjecture 1, which is known for polygonal paths, Conjecture 2 is still open even under the hypothesis of polygonal paths; the homological arguments alluded to previously now show that the number of inscribed squares in the periodic setting is *even* rather than *odd*, which is not enough to conclude the conjecture. (This flipping of parity from odd to even due to an infinite amount of oscillation is reminiscent of the “Eilenberg-Mazur swindle“, discussed in this previous post.)

I therefore tried to construct counterexamples to Conjecture 2. I began perturbatively, looking at curves that were small perturbations of constant functions. After some initial Taylor expansion, I was blocked from forming such a counterexample because an inspection of the leading Taylor coefficients required one to construct a continuous periodic function of mean zero that never vanished, which of course was impossible by the intermediate value theorem. I kept expanding to higher and higher order to try to evade this obstruction (this, incidentally, was when I discovered this cute application of Lagrange reversion) but no matter how high an accuracy I went (I think I ended up expanding to sixth order in a perturbative parameter before figuring out what was going on!), this obstruction kept resurfacing again and again. I eventually figured out that this obstruction was being caused by a “conserved integral of motion” for both Conjecture 2 and Conjecture 1, which can in fact be used to largely rule out perturbative constructions. This yielded a new positive result for both conjectures:

We sketch the proof of Theorem 3(i) as follows (the proof of Theorem 3(ii) is very similar). Let be the curve , thus traverses one of the two graphs that comprise . For each time , there is a unique square with first vertex (and the other three vertices, traversed in anticlockwise order, denoted ) such that also lies in the graph of and also lies in the graph of (actually for technical reasons we have to extend by constants to all of in order for this claim to be true). To see this, we simply rotate the graph of clockwise by around , where (by the Lipschitz hypotheses) it must hit the graph of in a unique point, which is , and which then determines the other two vertices of the square. The curve has the same starting and ending point as the graph of or ; using the Lipschitz hypothesis one can show this graph is simple. If the curve ever hits the graph of other than at the endpoints, we have created an inscribed square, so we may assume for contradiction that avoids the graph of , and hence by the Jordan curve theorem the two curves enclose some non-empty bounded open region .

Now for the conserved integral of motion. If we integrate the -form on each of the four curves , we obtain the identity

This identity can be established by the following calculation: one can parameterise

for some Lipschitz functions ; thus for instance . Inserting these parameterisations and doing some canceling, one can write the above integral as

which vanishes because (which represent the sidelengths of the squares determined by vanish at the endpoints .

Using this conserved integral of motion, one can show that

which by Stokes’ theorem then implies that the bounded open region mentioned previously has zero area, which is absurd.

This argument hinged on the curve being simple, so that the Jordan curve theorem could apply. Once one left the perturbative regime of curves of small Lipschitz constant, it became possible for to be self-crossing, but nevertheless there still seemed to be some sort of integral obstruction. I eventually isolated the problem in the form of a strengthened version of Conjecture 2:

Conjecture 4 (Area formulation of square peg problem)Let be simple closed piecewise linear curves of winding number obeying the area identity(note the -form is still well defined on the cylinder ; note also that the curves are allowed to cross each other.) Then there exists a (possibly degenerate) square with vertices (traversed in anticlockwise order) lying on respectively.

It is not difficult to see that Conjecture 4 implies Conjecture 2. Actually I believe that the converse implication is at least morally true, in that any counterexample to Conjecture 4 can be eventually transformed to a counterexample to Conjecture 2 and Conjecture 1. The conserved integral of motion argument can establish Conjecture 4 in many cases, for instance if are graphs of functions of Lipschitz constant less than one.

Conjecture 4 has a model special case, when one of the is assumed to just be a horizontal loop. In this case, the problem collapses to that of producing an intersection between two three-dimensional subsets of a six-dimensional space, rather than to four-dimensional subsets of an eight-dimensional space. More precisely, some elementary transformations reveal that this special case of Conjecture 4 can be formulated in the following fashion in which the geometric notion of a square is replaced by the additive notion of a triple of real numbers summing to zero:

Conjecture 5 (Special case of area formulation)Let be simple closed piecewise linear curves of winding number obeying the area identityThen there exist and with such that for .

This conjecture is easy to establish if one of the curves, say , is the graph of some piecewise linear function , since in that case the curve and the curve enclose the same area in the sense that , and hence must intersect by the Jordan curve theorem (otherwise they would enclose a non-zero amount of area between them), giving the claim. But when none of the are graphs, the situation becomes combinatorially more complicated.

Using some elementary homological arguments (e.g. breaking up closed -cycles into closed paths) and working with a generic horizontal slice of the curves, I was able to show that Conjecture 5 was equivalent to a one-dimensional problem that was largely combinatorial in nature, revolving around the sign patterns of various triple sums with drawn from various finite sets of reals.

Conjecture 6 (Combinatorial form)Let be odd natural numbers, and for each , let be distinct real numbers; we adopt the convention that . Assume the following axioms:

- (i) For any , the sums are non-zero.
- (ii) (Non-crossing) For any and with the same parity, the pairs and are non-crossing in the sense that
- (iii) (Non-crossing sums) For any , , of the same parity, one has
Then one has

Roughly speaking, Conjecture 6 and Conjecture 5 are connected by constructing curves to connect to for by various paths, which either lie to the right of the axis (when is odd) or to the left of the axis (when is even). The axiom (ii) is asserting that the numbers are ordered according to the permutation of a meander (formed by gluing together two non-crossing perfect matchings).

Using various *ad hoc* arguments involving “winding numbers”, it is possible to prove this conjecture in many cases (e.g. if one of the is at most ), to the extent that I have now become confident that this conjecture is true (and have now come full circle from trying to disprove Conjecture 1 to now believing that this conjecture holds also). But it seems that there is some non-trivial combinatorial argument to be made if one is to prove this conjecture; purely homological arguments seem to partially resolve the problem, but are not sufficient by themselves.

While I was not able to resolve the square peg problem, I think these results do provide a roadmap to attacking it, first by focusing on the combinatorial conjecture in Conjecture 6 (or its equivalent form in Conjecture 5), then after that is resolved moving on to Conjecture 4, and then finally to Conjecture 1.

## Recent Comments