You are currently browsing the category archive for the ‘math.CO’ category.
Rachel Greenfeld and I have just uploaded to the arXiv our preprint “Undecidable translational tilings with only two tiles, or one nonabelian tile“. This paper studies the following question: given a finitely generated group , a (periodic) subset of , and finite sets in , is it possible to tile by translations of the tiles ? That is to say, is there a solution to the (translational) tiling equation
for some subsets of , where denotes the set of sums if the sums are all disjoint (and is undefined otherwise), and denotes disjoint union. (One can also write the tiling equation in the language of convolutions as .)A bit more specifically, the paper studies the decidability of the above question. There are two slightly different types of decidability one could consider here:
- Logical decidability. For a given , one can ask whether the solvability of the tiling equation (1) is provable or disprovable in ZFC (where we encode all the data by appropriate constructions in ZFC). If this is the case we say that the tiling equation (1) (or more precisely, the solvability of this equation) is logically decidable, otherwise it is logically undecidable.
- Algorithmic decidability. For data in some specified class (and encoded somehow as binary strings), one can ask whether the solvability of the tiling equation (1) can be correctly determined for all choices of data in this class by the output of some Turing machine that takes the data as input (encoded as a binary string) and halts in finite time, returning either YES if the equation can be solved or NO otherwise. If this is the case, we say the tiling problem of solving (1) for data in the given class is algorithmically decidable, otherwise it is algorithmically undecidable.
Note that the notion of logical decidability is “pointwise” in the sense that it pertains to a single choice of data , whereas the notion of algorithmic decidability pertains instead to classes of data, and is only interesting when this class is infinite. Indeed, any tiling problem with a finite class of data is trivially decidable because one could simply code a Turing machine that is basically a lookup table that returns the correct answer for each choice of data in the class. (This is akin to how a student with a good memory could pass any exam if the questions are drawn from a finite list, merely by memorising an answer key for that list of questions.)
The two notions are related as follows: if a tiling problem (1) is algorithmically undecidable for some class of data, then the tiling equation must be logically undecidable for at least one choice of data for this class. For if this is not the case, one could algorithmically decide the tiling problem by searching for proofs or disproofs that the equation (1) is solvable for a given choice of data; the logical decidability of all such solvability questions will ensure that this algorithm always terminates in finite time.
One can use the Gödel completeness theorem to interpret logical decidability in terms of universes (also known as structures or models) of ZFC. In addition to the “standard” universe of sets that we believe satisfies the axioms of ZFC, there are also other “nonstandard” universes that also obey the axioms of ZFC. If the solvability of a tiling equation (1) is logically undecidable, this means that such a tiling exists in some universes of ZFC, but not in others.
(To continue the exam analogy, we thus see that a yes-no exam question is logically undecidable if the answer to the question is yes in some parallel universes, but not in others. A course syllabus is algorithmically undecidable if there is no way to prepare for the final exam for the course in a way that guarantees a perfect score (in the standard universe).)
Questions of decidability are also related to the notion of aperiodicity. For a given , a tiling equation (1) is said to be aperiodic if the equation (1) is solvable (in the standard universe of ZFC), but none of the solutions (in that universe) are completely periodic (i.e., there are no solutions where all of the are periodic). Perhaps the most well-known example of an aperiodic tiling (in the context of , and using rotations as well as translations) come from the Penrose tilings, but there are many others besides.
It was (essentially) observed by Hao Wang in the 1960s that if a tiling equation is logically undecidable, then it must necessarily be aperiodic. Indeed, if a tiling equation fails to be aperiodic, then (in the standard universe) either there is a periodic tiling, or there are no tilings whatsoever. In the former case, the periodic tiling can be used to give a finite proof that the tiling equation is solvable; in the latter case, the compactness theorem implies that there is some finite fragment of that is not compatible with being tiled by , and this provides a finite proof that the tiling equation is unsolvable. Thus in either case the tiling equation is logically decidable.
This observation of Wang clarifies somewhat how logically undecidable tiling equations behave in the various universes of ZFC. In the standard universe, tilings exist, but none of them will be periodic. In nonstandard universes, tilings may or may not exist, and the tilings that do exist may be periodic (albeit with a nonstandard period); but there must be at least one universe in which no tiling exists at all.
In one dimension when (or more generally with a finite group), a simple pigeonholing argument shows that no tiling equations are aperiodic, and hence all tiling equations are decidable. However the situation changes in two dimensions. In 1966, Berger (a student of Wang) famously showed that there exist tiling equations (1) in the discrete plane that are aperiodic, or even logically undecidable; in fact he showed that the tiling problem in this case (with arbitrary choices of data ) was algorithmically undecidable. (Strictly speaking, Berger established this for a variant of the tiling problem known as the domino problem, but later work of Golomb showed that the domino problem could be easily encoded within the tiling problem.) This was accomplished by encoding the halting problem for Turing machines into the tiling problem (or domino problem); the latter is well known to be algorithmically undecidable (and thus have logically undecidable instances), and so the latter does also. However, the number of tiles required for Berger’s construction was quite large: his construction of an aperiodic tiling required tiles, and his construction of a logically undecidable tiling required an even larger (and not explicitly specified) collection of tiles. Subsequent work by many authors did reduce the number of tiles required; in the setting, the current world record for the fewest number of tiles in an aperiodic tiling is (due to Amman, Grunbaum, and Shephard) and for a logically undecidable tiling is (due to Ollinger). On the other hand, it is conjectured (see Grunbaum-Shephard and Lagarias-Wang) that one cannot lower all the way to :
Conjecture 1 (Periodic tiling conjecture) If is a periodic subset of a finitely generated abelian group , and is a finite subset of , then the tiling equation is not aperiodic.
This conjecture is known to be true in two dimensions (by work of Bhattacharya when , and more recently by us when ), but remains open in higher dimensions. By the preceding discussion, the conjecture implies that every tiling equation with a single tile is logically decidable, and the problem of whether a given periodic set can be tiled by a single tile is algorithmically decidable.
In this paper we show on the other hand that aperiodic and undecidable tilings exist when , at least if one is permitted to enlarge the group a bit:
Theorem 2 (Logically undecidable tilings)
- (i) There exists a group of the form for some finite abelian , a subset of , and finite sets such that the tiling equation is logically undecidable (and hence also aperiodic).
- (ii) There exists a dimension , a periodic subset of , and finite sets such that tiling equation is logically undecidable (and hence also aperiodic).
- (iii) There exists a non-abelian finite group (with the group law still written additively), a subset of , and a finite set such that the nonabelian tiling equation is logically undecidable (and hence also aperiodic).
We also have algorithmic versions of this theorem. For instance, the algorithmic version of (i) is that the problem of determining solvability of the tiling equation for a given choice of finite abelian group , subset of , and finite sets is algorithmically undecidable. Similarly for (ii), (iii).
This result (together with a negative result discussed below) suggest to us that there is a significant qualitative difference in the theory of tiling by a single (abelian) tile, and the theory of tiling with multiple tiles (or one non-abelian tile). (The positive results on the periodic tiling conjecture certainly rely heavily on the fact that there is only one tile, in particular there is a “dilation lemma” that is only available in this setting that is of key importance in the two dimensional theory.) It would be nice to eliminate the group from (i) (or to set in (ii)), but I think this would require a fairly significant modification of our methods.
Like many other undecidability results, the proof of Theorem 2 proceeds by a sequence of reductions, in which the undecidability of one problem is shown to follow from the undecidability of another, more “expressive” problem that can be encoded inside the original problem, until one reaches a problem that is so expressive that it encodes a problem already known to be undecidable. Indeed, all three undecidability results are ultimately obtained from Berger’s undecidability result on the domino problem.
The first step in increasing expressiveness is to observe that the undecidability of a single tiling equation follows from the undecidability of a system of tiling equations. More precisely, suppose we have non-empty finite subsets of a finitely generated group for and , as well as periodic sets of for , such that it is logically undecidable whether the system of tiling equations
for has no solution in . Then, for any , we can “stack” these equations into a single tiling equation in the larger group , and specifically to the equation where and It is a routine exercise to check that the system of equations (2) admits a solution in if and only if the single equation (3) admits a equation in . Thus, to prove the undecidability of a single equation of the form (3) it suffices to establish undecidability of a system of the form (2); note here how the freedom to select the auxiliary group is important here.We view systems of the form (2) as belonging to a kind of “language” in which each equation in the system is a “sentence” in the language imposing additional constraints on a tiling. One can now pick and choose various sentences in this language to try to encode various interesting problems. For instance, one can encode the concept of a function taking values in a finite group as a single tiling equation
since the solutions to this equation are precisely the graphs of a function . By adding more tiling equations to this equation to form a larger system, we can start imposing additional constraints on this function . For instance, if is a coset of some subgroup of , we can impose the additional equation to impose the additional constraint that for all , if we desire. If happens to contain two distinct elements , and , then the additional equation imposes the additional constraints that for all , and additionally that for all .This begins to resemble the equations that come up in the domino problem. Here one has a finite set of Wang tiles – unit squares where each of the four sides is colored with a color (corresponding to the four cardinal directions North, South, East, and West) from some finite set of colors. The domino problem is then to tile the plane with copies of these tiles in such a way that adjacent sides match. In terms of equations, one is seeking to find functions obeying the pointwise constraint
for all where is the set of colors associated to the set of Wang tiles being used, and the matching constraints for all . As it turns out, the pointwise constraint (7) can be encoded by tiling equations that are fancier versions of (4), (5), (6) that involve only one unknown tiling set , but in order to encode the matching constraints (8) we were forced to introduce a second tile (or work with nonabelian tiling equations). This appears to be an inherent feature of the method, since we found a partial rigidity result for tilings of one tile in one dimension that obstructs this encoding strategy from working when one only has one tile available. The result is as follows:
Proposition 3 (Swapping property) Consider the solutions to a tiling equation in a one-dimensional group (with a finite abelian group, finite, and periodic). Suppose there are two solutions to this equation that agree on the left in the sense that For any function , define the “swap” of and to be the set Then also solves the equation (9).
One can think of and as “genes” with “nucleotides” , at each position , and is a new gene formed by choosing one of the nucleotides from the “parent” genes , at each position. The above proposition then says that the solutions to the equation (9) must be closed under “genetic transfer” among any pair of genes that agree on the left. This seems to present an obstruction to trying to encode equation such as
for two functions (say), which is a toy version of the matching constraint (8), since the class of solutions to this equation turns out not to obey this swapping property. On the other hand, it is easy to encode such equations using two tiles instead of one, and an elaboration of this construction is used to prove our main theorem.In the modern theory of higher order Fourier analysis, a key role are played by the Gowers uniformity norms for . For finitely supported functions , one can define the (non-normalised) Gowers norm by the formula
where denotes complex conjugation, and then on any discrete interval and any function we can then define the (normalised) Gowers norm where is the extension of by zero to all of . Thus for instance (which technically makes a seminorm rather than a norm), and one can calculate where , and we use the averaging notation .The significance of the Gowers norms is that they control other multilinear forms that show up in additive combinatorics. Given any polynomials and functions , we define the multilinear form
(assuming that the denominator is finite and non-zero). Thus for instance where we view as formal (indeterminate) variables, and are understood to be extended by zero to all of . These forms are used to count patterns in various sets; for instance, the quantity is closely related to the number of length three arithmetic progressions contained in . Let us informally say that a form is controlled by the norm if the form is small whenever are -bounded functions with at least one of the small in norm. This definition was made more precise by Gowers and Wolf, who then defined the true complexity of a form to be the least such that is controlled by the norm. For instance,- and have true complexity ;
- has true complexity ;
- has true complexity ;
- The form (which among other things could be used to count twin primes) has infinite true complexity (which is quite unfortunate for applications).
Gowers and Wolf formulated a conjecture on what this complexity should be, at least for linear polynomials ; Ben Green and I thought we had resolved this conjecture back in 2010, though it turned out there was a subtle gap in our arguments and we were only able to resolve the conjecture in a partial range of cases. However, the full conjecture was recently resolved by Daniel Altman.
The (semi-)norm is so weak that it barely controls any averages at all. For instance the average
is not controlled by the semi-norm: it is perfectly possible for a -bounded function to even have vanishing norm but have large value of (consider for instance the parity function ).Because of this, I propose inserting an additional norm in the Gowers uniformity norm hierarchy between the and norms, which I will call the (or “profinite “) norm:
where ranges over all arithmetic progressions in . This can easily be seen to be a norm on functions that controls the norm. It is also basically controlled by the norm for -bounded functions ; indeed, if is an arithmetic progression in of some spacing , then we can write as the intersection of an interval with a residue class modulo , and from Fourier expansion we have If we let be a standard bump function supported on with total mass and is a parameter then (extending by zero outside of ), as can be seen by using the triangle inequality and the estimate After some Fourier expansion of we now have Writing as a linear combination of and using the Gowers–Cauchy–Schwarz inequality, we conclude hence on optimising in we have Forms which are controlled by the norm (but not ) would then have their true complexity adjusted to with this insertion.The norm recently appeared implicitly in work of Peluse and Prendiville, who showed that the form had true complexity in this notation (with polynomially strong bounds). [Actually, strictly speaking this control was only shown for the third function ; for the first two functions one needs to localize the norm to intervals of length . But I will ignore this technical point to keep the exposition simple.] The weaker claim that has true complexity is substantially easier to prove (one can apply the circle method together with Gauss sum estimates).
The well known inverse theorem for the norm tells us that if a -bounded function has norm at least for some , then there is a Fourier phase such that
this follows easily from (1) and Plancherel’s theorem. Conversely, from the Gowers–Cauchy–Schwarz inequality one hasFor one has a trivial inverse theorem; by definition, the norm of is at least if and only if
Thus the frequency appearing in the inverse theorem can be taken to be zero when working instead with the norm.For one has the intermediate situation in which the frequency is not taken to be zero, but is instead major arc. Indeed, suppose that is -bounded with , thus
for some progression . This forces the spacing of this progression to be . We write the above inequality as for some residue class and some interval . By Fourier expansion and the triangle inequality we then have for some integer . Convolving by for a small multiple of and a Schwartz function of unit mass with Fourier transform supported on , we have The Fourier transform of is bounded by and supported on , thus by Fourier expansion and the triangle inequality we have for some , so in particular . Thus we have for some of the major arc form with . Conversely, for of this form, some routine summation by parts gives the bound so if (2) holds for a -bounded then one must have .Here is a diagram showing some of the control relationships between various Gowers norms, multilinear forms, and duals of classes of functions (where each class of functions induces a dual norm :
Here I have included the three classes of functions that one can choose from for the inverse theorem, namely degree two nilsequences, bracket quadratic phases, and local quadratic phases, as well as the more narrow class of globally quadratic phases.
The Gowers norms have counterparts for measure-preserving systems , known as Host-Kra seminorms. The norm can be defined for as
and the norm can be defined as The seminorm is orthogonal to the invariant factor (generated by the (almost everywhere) invariant measurable subsets of ) in the sense that a function has vanishing seminorm if and only if it is orthogonal to all -measurable (bounded) functions. Similarly, the norm is orthogonal to the Kronecker factor , generated by the eigenfunctions of (that is to say, those obeying an identity for some -invariant ); for ergodic systems, it is the largest factor isomorphic to rotation on a compact abelian group. In analogy to the Gowers norm, one can then define the Host-Kra seminorm by it is orthogonal to the profinite factor , generated by the periodic sets of (or equivalently, by those eigenfunctions whose eigenvalue is a root of unity); for ergodic systems, it is the largest factor isomorphic to rotation on a profinite abelian group.The (classical) Möbius function is the unique function that obeys the classical Möbius inversion formula:
Proposition 1 (Classical Möbius inversion) Let be functions from the natural numbers to an additive group . Then the following two claims are equivalent:
- (i) for all .
- (ii) for all .
There is a generalisation of this formula to (finite) posets, due to Hall, in which one sums over chains in the poset:
Proposition 2 (Poset Möbius inversion) Let be a finite poset, and let be functions from that poset to an additive group . Then the following two claims are equivalent:(Note from the finite nature of that the inner sum in (ii) is vacuous for all but finitely many .)
- (i) for all , where is understood to range in .
- (ii) for all , where in the inner sum are understood to range in with the indicated ordering.
Comparing Proposition 2 with Proposition 1, it is natural to refer to the function as the Möbius function of the poset; the condition (ii) can then be written as
Proof: If (i) holds, then we have for any . Iterating this we obtain (ii). Conversely, from (ii) and separating out the term, and grouping all the other terms based on the value of , we obtain (1), and hence (i).In fact it is not completely necessary that the poset be finite; an inspection of the proof shows that it suffices that every element of the poset has only finitely many predecessors .
It is not difficult to see that Proposition 2 includes Proposition 1 as a special case, after verifying the combinatorial fact that the quantity
is equal to when divides , and vanishes otherwise.I recently discovered that Proposition 2 can also lead to a useful variant of the inclusion-exclusion principle. The classical version of this principle can be phrased in terms of indicator functions: if are subsets of some set , then
In particular, if there is a finite measure on for which are all measurable, we haveOne drawback of this formula is that there are exponentially many terms on the right-hand side: of them, in fact. However, in many cases of interest there are “collisions” between the intersections (for instance, perhaps many of the pairwise intersections agree), in which case there is an opportunity to collect terms and hopefully achieve some cancellation. It turns out that it is possible to use Proposition 2 to do this, in which one only needs to sum over chains in the resulting poset of intersections:
Proposition 3 (Hall-type inclusion-exclusion principle) Let be subsets of some set , and let be the finite poset formed by intersections of some of the (with the convention that is the empty intersection), ordered by set inclusion. Then for any , one has where are understood to range in . In particular (setting to be the empty intersection) if the are all proper subsets of then we have In particular, if there is a finite measure on for which are all measurable, we have
Using the Möbius function on the poset , one can write these formulae as
andProof: It suffices to establish (2) (to derive (3) from (2) observe that all the are contained in one of the , so the effect of may be absorbed into ). Applying Proposition 2, this is equivalent to the assertion that
for all . But this amounts to the assertion that for each , there is precisely one in with the property that and for any in , namely one can take to be the intersection of all in such that contains .
Example 4 If with , and are all distinct, then we have for any finite measure on that makes measurable that due to the four chains , , , of length one, and the three chains , , of length two. Note that this expansion just has six terms in it, as opposed to the given by the usual inclusion-exclusion formula, though of course one can reduce the number of terms by combining the factors. This may not seem particularly impressive, especially if one views the term as really being three terms instead of one, but if we add a fourth set with for all , the formula now becomes and we begin to see more cancellation as we now have just seven terms (or ten if we count as four terms) instead of terms.
Example 5 (Variant of Legendre sieve) If are natural numbers, and is some sequence of complex numbers with only finitely many terms non-zero, then by applying the above proposition to the sets and with equal to counting measure weighted by the we obtain a variant of the Legendre sieve where range over the set formed by taking least common multiples of the (with the understanding that the empty least common multiple is ), and denotes the assertion that divides but is strictly less than . I am curious to know of this version of the Legendre sieve already appears in the literature (and similarly for the other applications of Proposition 2 given here).
If the poset has bounded depth then the number of terms in Proposition 3 can end up being just polynomially large in rather than exponentially large. Indeed, if all chains in have length at most then the number of terms here is at most . (The examples (4), (5) are ones in which the depth is equal to two.) I hope to report in a later post on how this version of inclusion-exclusion with polynomially many terms can be useful in an application.
Actually in our application we need an abstraction of the above formula, in which the indicator functions are replaced by more abstract idempotents:
Proposition 6 (Hall-type inclusion-exclusion principle for idempotents) Let be pairwise commuting elements of some ring with identity, which are all idempotent (thus for ). Let be the finite poset formed by products of the (with the convention that is the empty product), ordered by declaring when (note that all the elements of are idempotent so this is a partial ordering). Then for any , one has where are understood to range in . In particular (setting ) if all the are not equal to then we have
Morally speaking this proposition is equivalent to the previous one after applying a “spectral theorem” to simultaneously diagonalise all of the , but it is quicker to just adapt the previous proof to establish this proposition directly. Using the Möbius function for , we can rewrite these formulae as
andProof: Again it suffices to verify (6). Using Proposition 2 as before, it suffices to show that
for all (all sums and products are understood to range in ). We can expand where ranges over all subsets of that contain . For such an , if we write , then is the greatest lower bound of , and we observe that vanishes whenever fails to contain some with . Thus the only that give non-zero contributions to (8) are the intervals of the form for some (which then forms the greatest lower bound for that interval), and the claim (7) follows (after noting that for any ).
Laura Cladek and I have just uploaded to the arXiv our paper “Additive energy of regular measures in one and higher dimensions, and the fractal uncertainty principle“. This paper concerns a continuous version of the notion of additive energy. Given a finite measure on and a scale , define the energy at scale to be the quantity
where is the product measure on formed from four copies of the measure on . We will be interested in Cantor-type measures , supported on a compact set and obeying the Ahlfors-David regularity condition for all balls and some constants , as well as the matching lower bound when whenever . One should think of as a -dimensional fractal set, and as some vaguely self-similar measure on this set.Note that once one fixes , the variable in (1) is constrained to a ball of radius , hence we obtain the trivial upper bound
If the set contains a lot of “additive structure”, one can expect this bound to be basically sharp; for instance, if is an integer, is a -dimensional unit disk, and is Lebesgue measure on this disk, one can verify that (where we allow implied constants to depend on . However we show that if the dimension is non-integer, then one obtains a gain:
Theorem 1 If is not an integer, and are as above, then for some depending only on .
Informally, this asserts that Ahlfors-David regular fractal sets of non-integer dimension cannot behave as if they are approximately closed under addition. In fact the gain we obtain is quasipolynomial in the regularity constant :
(We also obtain a localised version in which the regularity condition is only required to hold at scales between and .) Such a result was previously obtained (with more explicit values of the implied constants) in the one-dimensional case by Dyatlov and Zahl; but in higher dimensions there does not appear to have been any results for this general class of sets and measures . In the paper of Dyatlov and Zahl it is noted that some dependence on is necessary; in particular, cannot be much better than . This reflects the fact that there are fractal sets that do behave reasonably well with respect to addition (basically because they are built out of long arithmetic progressions at many scales); however, such sets are not very Ahlfors-David regular. Among other things, this result readily implies a dimension expansion result for any non-degenerate smooth map , including the sum map and (in one dimension) the product map , where the non-degeneracy condition required is that the gradients are invertible for every . We refer to the paper for the formal statement.Our higher-dimensional argument shares many features in common with that of Dyatlov and Zahl, notably a reliance on the modern tools of additive combinatorics (and specifically the Bogulybov-Ruzsa lemma of Sanders). However, in one dimension we were also able to find a completely elementary argument, avoiding any particularly advanced additive combinatorics and instead primarily exploiting the order-theoretic properties of the real line, that gave a superior value of , namely
One of the main reasons for obtaining such improved energy bounds is that they imply a fractal uncertainty principle in some regimes. We focus attention on the model case of obtaining such an uncertainty principle for the semiclassical Fourier transform
where is a small parameter. If are as above, and denotes the -neighbourhood of , then from the Hausdorff-Young inequality one obtains the trivial bound (There are also variants involving pairs of sets , but for simplicity we focus on the uncertainty principle for a single set .) The fractal uncertainty principle, when it applies, asserts that one can improve this to for some ; informally, this asserts that a function and its Fourier transform cannot simultaneously be concentrated in the set when , and that a function cannot be concentrated on and have its Fourier transform be of maximum size on when . A modification of the disk example mentioned previously shows that such a fractal uncertainty principle cannot hold if is an integer. However, in one dimension, the fractal uncertainty principle is known to hold for all . The above-mentioned results of Dyatlov and Zahl were able to establish this for close to , and the remaining cases and were later established by Bourgain-Dyatlov and Dyatlov-Jin respectively. Such uncertainty principles have applications to hyperbolic dynamics, in particular in establishing spectral gaps for certain Selberg zeta functions.It remains a largely open problem to establish a fractal uncertainty principle in higher dimensions. Our results allow one to establish such a principle when the dimension is close to , and is assumed to be odd (to make a non-integer). There is also work of Han and Schlag that obtains such a principle when one of the copies of is assumed to have a product structure. We hope to obtain further higher-dimensional fractal uncertainty principles in subsequent work.
We now sketch how our main theorem is proved. In both one dimension and higher dimensions, the main point is to get a preliminary improvement
over the trivial bound (2) for any small , provided is sufficiently small depending on ; one can then iterate this bound by a fairly standard “induction on scales” argument (which roughly speaking can be used to show that energies behave somewhat multiplicatively in the scale parameter ) to propagate the bound to a power gain at smaller scales. We found that a particularly clean way to run the induction on scales was via use of the Gowers uniformity norm , and particularly via a clean Fubini-type inequality (ultimately proven using the Gowers-Cauchy-Schwarz inequality) that allows one to “decouple” coarse and fine scale aspects of the Gowers norms (and hence of additive energies).It remains to obtain the preliminary improvement. In one dimension this is done by identifying some “left edges” of the set that supports : intervals that intersect , but such that a large interval just to the left of this interval is disjoint from . Here is a large constant and is a scale parameter. It is not difficult to show (using in particular the Archimedean nature of the real line) that if one has the Ahlfors-David regularity condition for some then left edges exist in abundance at every scale; for instance most points of would be expected to lie in quite a few of these left edges (much as most elements of, say, the ternary Cantor set would be expected to contain a lot of s in their base expansion). In particular, most pairs would be expected to lie in a pair of left edges of equal length. The key point is then that if lies in such a pair with , then there are relatively few pairs at distance from for which one has the relation , because will both tend to be to the right of respectively. This causes a decrement in the energy at scale , and by carefully combining all these energy decrements one can eventually cobble together the energy bound (3).
We were not able to make this argument work in higher dimension (though perhaps the cases and might not be completely out of reach from these methods). Instead we return to additive combinatorics methods. If the claim (3) failed, then by applying the Balog-Szemeredi-Gowers theorem we can show that the set has high correlation with an approximate group , and hence (by the aforementioned Bogulybov-Ruzsa type theorem of Sanders, which is the main source of the quasipolynomial bounds in our final exponent) will exhibit an approximate “symmetry” along some non-trivial arithmetic progression of some spacing length and some diameter . The -neighbourhood of will then resemble the union of parallel “cylinders” of dimensions . If we focus on a typical -ball of , the set now resembles a Cartesian product of an interval of length with a subset of a -dimensional hyperplane, which behaves approximately like an Ahlfors-David regular set of dimension (this already lets us conclude a contradiction if ). Note that if the original dimension was non-integer then this new dimension will also be non-integer. It is then possible to contradict the failure of (3) by appealing to a suitable induction hypothesis at one lower dimension.
Ben Green and I have updated our paper “An arithmetic regularity lemma, an associated counting lemma, and applications” to account for a somewhat serious issue with the paper that was pointed out to us recently by Daniel Altman. This paper contains two core theorems:
- An “arithmetic regularity lemma” that, roughly speaking, decomposes an arbitrary bounded sequence on an interval as an “irrational nilsequence” of controlled complexity, plus some “negligible” errors (where one uses the Gowers uniformity norm as the main norm to control the neglibility of the error); and
- An “arithmetic counting lemma” that gives an asymptotic formula for counting various averages for various affine-linear forms when the functions are given by irrational nilsequences.
The combination of the two theorems is then used to address various questions in additive combinatorics.
There are no direct issues with the arithmetic regularity lemma. However, it turns out that the arithmetic counting lemma is only true if one imposes an additional property (which we call the “flag property”) on the affine-linear forms . Without this property, there does not appear to be a clean asymptotic formula for these averages if the only hypothesis one places on the underlying nilsequences is irrationality. Thus when trying to understand the asymptotics of averages involving linear forms that do not obey the flag property, the paradigm of understanding these averages via a combination of the regularity lemma and a counting lemma seems to require some significant revision (in particular, one would probably have to replace the existing regularity lemma with some variant, despite the fact that the lemma is still technically true in this setting). Fortunately, for most applications studied to date (including the important subclass of translation-invariant affine forms), the flag property holds; however our claim in the paper to have resolved a conjecture of Gowers and Wolf on the true complexity of systems of affine forms must now be narrowed, as our methods only verify this conjecture under the assumption of the flag property.
In a bit more detail: the asymptotic formula for our counting lemma involved some finite-dimensional vector spaces for various natural numbers , defined as the linear span of the vectors as ranges over the parameter space . Roughly speaking, these spaces encode some constraints one would expect to see amongst the forms . For instance, in the case of length four arithmetic progressions when , , and
for , then is spanned by the vectors and and can thus be described as the two-dimensional linear space while is spanned by the vectors , , and can be described as the hyperplane As a special case of the counting lemma, we can check that if takes the form for some irrational , some arbitrary , and some smooth , then the limiting value of the average as is equal to which reflects the constraints and These constraints follow from the descriptions (1), (2), using the containment to dispense with the lower order term (which then plays no further role in the analysis).The arguments in our paper turn out to be perfectly correct under the assumption of the “flag property” that for all . The problem is that the flag property turns out to not always hold. A counterexample, provided by Daniel Altman, involves the four linear forms
Here it turns out that and and is no longer contained in . The analogue of the asymptotic formula given previously for is then valid when vanishes, but not when is non-zero, because the identity holds in the former case but not the latter. Thus the output of any purported arithmetic regularity lemma in this case is now sensitive to the lower order terms of the nilsequence and cannot be described in a uniform fashion for all “irrational” sequences. There should still be some sort of formula for the asymptotics from the general equidistribution theory of nilsequences, but it could be considerably more complicated than what is presented in this paper.Fortunately, the flag property does hold in several key cases, most notably the translation invariant case when contains , as well as “complexity one” cases. Nevertheless non-flag property systems of affine forms do exist, thus limiting the range of applicability of the techniques in this paper. In particular, the conjecture of Gowers and Wolf (Theorem 1.13 in the paper) is now open again in the non-flag property case.
Rachel Greenfeld and I have just uploaded to the arXiv our paper “The structure of translational tilings in “. This paper studies the tilings of a finite tile in a standard lattice , that is to say sets (which we call tiling sets) such that every element of lies in exactly one of the translates of . We also consider more general tilings of level for a natural number (several of our results consider an even more general setting in which is periodic but allowed to be non-constant).
In many cases the tiling set will be periodic (by which we mean translation invariant with respect to some lattice (a finite index subgroup) of ). For instance one simple example of a tiling is when is the unit square and is the lattice . However one can modify some tilings to make them less periodic. For instance, keeping one also has the tiling set
where is an arbitrary function. This tiling set is periodic in a single direction , but is not doubly periodic. For the slightly modified tile , the set for arbitrary can be verified to be a tiling set, which in general will not exhibit any periodicity whatsoever; however, it is weakly periodic in the sense that it is the disjoint union of finitely many sets, each of which is periodic in one direction.The most well known conjecture in this area is the Periodic Tiling Conjecture:
Conjecture 1 (Periodic tiling conjecture) If a finite tile has at least one tiling set, then it has a tiling set which is periodic.
This conjecture was stated explicitly by Lagarias and Wang, and also appears implicitly in this text of Grunbaum and Shepard. In one dimension there is a simple pigeonhole principle argument of Newman that shows that all tiling sets are in fact periodic, which certainly implies the periodic tiling conjecture in this case. The case was settled more recently by Bhattacharya, but the higher dimensional cases remain open in general.
We are able to obtain a new proof of Bhattacharya’s result that also gives some quantitative bounds on the periodic tiling set, which are polynomial in the diameter of the set if the cardinality of the tile is bounded:
Theorem 2 (Quantitative periodic tiling in ) If a finite tile has at least one tiling set, then it has a tiling set which is -periodic for some .
Among other things, this shows that the problem of deciding whether a given subset of of bounded cardinality tiles or not is in the NP complexity class with respect to the diameter . (Even the decidability of this problem was not known until the result of Bhattacharya.)
We also have a closely related structural theorem:
Theorem 3 (Quantitative weakly periodic tiling in ) Every tiling set of a finite tile is weakly periodic. In fact, the tiling set is the union of at most disjoint sets, each of which is periodic in a direction of magnitude .
We also have a new bound for the periodicity of tilings in :
Theorem 4 (Universal period for tilings in ) Let be finite, and normalized so that . Then every tiling set of is -periodic, where is the least common multiple of all primes up to , and is the least common multiple of the magnitudes of all .
We remark that the current best complexity bound of determining whether a subset of tiles or not is , due to Biro. It may be that the results in this paper can improve upon this bound, at least for tiles of bounded cardinality.
On the other hand, we discovered a genuine difference between level one tiling and higher level tiling, by locating a counterexample to the higher level analogue of (the qualitative version of) Theorem 3:
Theorem 5 (Counterexample) There exists an eight-element subset and a level tiling such that is not weakly periodic.
We do not know if there is a corresponding counterexample to the higher level periodic tiling conjecture (that if tiles at level , then there is a periodic tiling at the same level ). Note that it is important to keep the level fixed, since one trivially always has a periodic tiling at level from the identity .
The methods of Bhattacharya used the language of ergodic theory. Our investigations also originally used ergodic-theoretic and Fourier-analytic techniques, but we ultimately found combinatorial methods to be more effective in this problem (and in particular led to quite strong quantitative bounds). The engine powering all of our results is the following remarkable fact, valid in all dimensions:
Lemma 6 (Dilation lemma) Suppose that is a tiling of a finite tile . Then is also a tiling of the dilated tile for any coprime to , where is the least common multiple of all the primes up to .
Versions of this dilation lemma have previously appeared in work of Tijdeman and of Bhattacharya. We sketch a proof here. By the fundamental theorem of arithmetic and iteration it suffices to establish the case where is a prime . We need to show that . It suffices to show the claim , since both sides take values in . The convolution algebra (or group algebra) of finitely supported functions from to is a commutative algebra of characteristic , so we have the Frobenius identity for any . As a consequence we see that . The claim now follows by convolving the identity by further copies of .
In our paper we actually establish a more general version of the dilation lemma that can handle tilings of higher level or of a periodic set, and this stronger version is useful to get the best quantitative results, but for simplicity we focus attention just on the above simple special case of the dilation lemma.
By averaging over all in an arithmetic progression, one already gets a useful structural theorem for tilings in any dimension, which appears to be new despite being an easy consequence of Lemma 6:
Corollary 7 (Structure theorem for tilings) Suppose that is a tiling of a finite tile , where we normalize . Then we have a decomposition where each is a function that is periodic in the direction , where is the least common multiple of all the primes up to .
Proof: From Lemma 6 we have for any , where is the Kronecker delta at . Now average over (extracting a weak limit or generalised limit as necessary) to obtain the conclusion.
The identity (1) turns out to impose a lot of constraints on the functions , particularly in one and two dimensions. On one hand, one can work modulo to eliminate the and terms to obtain the equation
which in two dimensions in particular puts a lot of structure on each individual (roughly speaking it makes the behave in a polynomial fashion, after collecting commensurable terms). On the other hand we have the inequality which can be used to exclude “equidistributed” polynomial behavior after a certain amount of combinatorial analysis. Only a small amount of further argument is then needed to conclude Theorem 3 and Theorem 2.For level tilings the analogue of (2) becomes
which is a significantly weaker inequality and now no longer seems to prohibit “equidistributed” behavior. After some trial and error we were able to come up with a completely explicit example of a tiling that actually utilises equidistributed polynomials; indeed the tiling set we ended up with was a finite boolean combination of Bohr sets.We are currently studying what this machinery can tell us about tilings in higher dimensions, focusing initially on the three-dimensional case.
Abdul Basit, Artem Chernikov, Sergei Starchenko, Chiu-Minh Tran and I have uploaded to the arXiv our paper Zarankiewicz’s problem for semilinear hypergraphs. This paper is in the spirit of a number of results in extremal graph theory in which the bounds for various graph-theoretic problems or results can be greatly improved if one makes some additional hypotheses regarding the structure of the graph, for instance by requiring that the graph be “definable” with respect to some theory with good model-theoretic properties.
A basic motivating example is the question of counting the number of incidences between points and lines (or between points and other geometric objects). Suppose one has points and lines in a space. How many incidences can there be between these points and lines? The utterly trivial bound is , but by using the basic fact that two points determine a line (or two lines intersect in at most one point), a simple application of Cauchy-Schwarz improves this bound to . In graph theoretic terms, the point is that the bipartite incidence graph between points and lines does not contain a copy of (there does not exist two points and two lines that are all incident to each other). Without any other further hypotheses, this bound is basically sharp: consider for instance the collection of points and lines in a finite plane , that has incidences (one can make the situation more symmetric by working with a projective plane rather than an affine plane). If however one considers lines in the real plane , the famous Szemerédi-Trotter theorem improves the incidence bound further from to . Thus the incidence graph between real points and lines contains more structure than merely the absence of .
More generally, bounding on the size of bipartite graphs (or multipartite hypergraphs) not containing a copy of some complete bipartite subgraph (or in the hypergraph case) is known as Zarankiewicz’s problem. We have results for all and all orders of hypergraph, but for sake of this post I will focus on the bipartite case.
In our paper we improve the bound to a near-linear bound in the case that the incidence graph is “semilinear”. A model case occurs when one considers incidences between points and axis-parallel rectangles in the plane. Now the condition is not automatic (it is of course possible for two distinct points to both lie in two distinct rectangles), so we impose this condition by fiat:
Theorem 1 Suppose one has points and axis-parallel rectangles in the plane, whose incidence graph contains no ‘s, for some large .
- (i) The total number of incidences is .
- (ii) If all the rectangles are dyadic, the bound can be improved to .
- (iii) The bound in (ii) is best possible (up to the choice of implied constant).
We don’t know whether the bound in (i) is similarly tight for non-dyadic boxes; the usual tricks for reducing the non-dyadic case to the dyadic case strangely fail to apply here. One can generalise to higher dimensions, replacing rectangles by polytopes with faces in some fixed finite set of orientations, at the cost of adding several more logarithmic factors; also, one can replace the reals by other ordered division rings, and replace polytopes by other sets of bounded “semilinear descriptive complexity”, e.g., unions of boundedly many polytopes, or which are cut out by boundedly many functions that enjoy coordinatewise monotonicity properties. For certain specific graphs we can remove the logarithmic factors entirely. We refer to the preprint for precise details.
The proof techniques are combinatorial. The proof of (i) relies primarily on the order structure of to implement a “divide and conquer” strategy in which one can efficiently control incidences between points and rectangles by incidences between approximately points and boxes. For (ii) there is additional order-theoretic structure one can work with: first there is an easy pruning device to reduce to the case when no rectangle is completely contained inside another, and then one can impose the “tile partial order” in which one dyadic rectangle is less than another if and . The point is that this order is “locally linear” in the sense that for any two dyadic rectangles , the set is linearly ordered, and this can be exploited by elementary double counting arguments to obtain a bound which eventually becomes after optimising certain parameters in the argument. The proof also suggests how to construct the counterexample in (iii), which is achieved by an elementary iterative construction.
A family of sets for some is a sunflower if there is a core set contained in each of the such that the petal sets are disjoint. If , let denote the smallest natural number with the property that any family of distinct sets of cardinality at most contains distinct elements that form a sunflower. The celebrated Erdös-Rado theorem asserts that is finite; in fact Erdös and Rado gave the bounds
The sunflower conjecture asserts in fact that the upper bound can be improved to . This remains open at present despite much effort (including a Polymath project); after a long series of improvements to the upper bound, the best general bound known currently is for all , established in 2019 by Rao (building upon a recent breakthrough a month previously of Alweiss, Lovett, Wu, and Zhang). Here we remove the easy cases or in order to make the logarithmic factor a little cleaner.Rao’s argument used the Shannon noiseless coding theorem. It turns out that the argument can be arranged in the very slightly different language of Shannon entropy, and I would like to present it here. The argument proceeds by locating the core and petals of the sunflower separately (this strategy is also followed in Alweiss-Lovett-Wu-Zhang). In both cases the following definition will be key. In this post all random variables, such as random sets, will be understood to be discrete random variables taking values in a finite range. We always use boldface symbols to denote random variables, and non-boldface for deterministic quantities.
Definition 1 (Spread set) Let . A random set is said to be -spread if one has for all sets . A family of sets is said to be -spread if is non-empty and the random variable is -spread, where is drawn uniformly from .
The core can then be selected greedily in such a way that the remainder of a family becomes spread:
Lemma 2 (Locating the core) Let be a family of subsets of a finite set , each of cardinality at most , and let . Then there exists a “core” set of cardinality at most such that the set has cardinality at least , and such that the family is -spread. Furthermore, if and the are distinct, then .
Proof: We may assume is non-empty, as the claim is trivial otherwise. For any , define the quantity
and let be a subset of that maximizes . Since and when , we see that . If the are distinct and , then we also have when , thus in this case we have .Let be the set (3). Since , is non-empty. It remains to check that the family is -spread. But for any and drawn uniformly at random from one has
Observe that , and the probability is only non-empty when are disjoint, so that . The claim follows.In view of the above lemma, the bound (2) will then follow from
Proposition 3 (Locating the petals) Let be natural numbers, and suppose that for a sufficiently large constant . Let be a finite family of subsets of a finite set , each of cardinality at most which is -spread. Then there exist such that is disjoint.
Indeed, to prove (2), we assume that is a family of sets of cardinality greater than for some ; by discarding redundant elements and sets we may assume that is finite and that all the are contained in a common finite set . Apply Lemma 2 to find a set of cardinality such that the family is -spread. By Proposition 3 we can find such that are disjoint; since these sets have cardinality , this implies that the are distinct. Hence form a sunflower as required.
Remark 4 Proposition 3 is easy to prove if we strengthen the condition on to . In this case, we have for every , hence by the union bound we see that for any with there exists such that is disjoint from the set , which has cardinality at most . Iterating this, we obtain the conclusion of Proposition 3 in this case. This recovers a bound of the form , and by pursuing this idea a little further one can recover the original upper bound (1) of Erdös and Rado.
It remains to prove Proposition 3. In fact we can locate the petals one at a time, placing each petal inside a random set.
Proposition 5 (Locating a single petal) Let the notation and hypotheses be as in Proposition 3. Let be a random subset of , such that each lies in with an independent probability of . Then with probability greater than , contains one of the .
To see that Proposition 5 implies Proposition 3, we randomly partition into by placing each into one of the , chosen uniformly and independently at random. By Proposition 5 and the union bound, we see that with positive probability, it is simultaneously true for all that each contains one of the . Selecting one such for each , we obtain the required disjoint petals.
We will prove Proposition 5 by gradually increasing the density of the random set and arranging the sets to get quickly absorbed by this random set. The key iteration step is
Proposition 6 (Refinement inequality) Let and . Let be a random subset of a finite set which is -spread, and let be a random subset of independent of , such that each lies in with an independent probability of . Then there exists another -spread random subset of whose support is contained in the support of , such that and
Note that a direct application of the first moment method gives only the bound
but the point is that by switching from to an equivalent we can replace the factor by a quantity significantly smaller than .One can iterate the above proposition, repeatedly replacing with (noting that this preserves the -spread nature of ) to conclude
Corollary 7 (Iterated refinement inequality) Let , , and . Let be a random subset of a finite set which is -spread, and let be a random subset of independent of , such that each lies in with an independent probability of . Then there exists another random subset of with support contained in the support of , such that
Now we can prove Proposition 5. Let be chosen shortly. Applying Corollary 7 with drawn uniformly at random from the , and setting , or equivalently , we have
In particular, if we set , so that , then by choice of we have , hence In particular with probability at least , there must exist such that , giving the proposition.It remains to establish Proposition 6. This is the difficult step, and requires a clever way to find the variant of that has better containment properties in than does. The main trick is to make a conditional copy of that is conditionally independent of subject to the constraint . The point here is that this constrant implies the inclusions
and Because of the -spread hypothesis, it is hard for to contain any fixed large set. If we could apply this observation in the contrapositive to we could hope to get a good upper bound on the size of and hence on thanks to (4). One can also hope to improve such an upper bound by also employing (5), since it is also hard for the random set to contain a fixed large set. There are however difficulties with implementing this approach due to the fact that the random sets are coupled with in a moderately complicated fashion. In Rao’s argument a somewhat complicated encoding scheme was created to give information-theoretic control on these random variables; below the fold we accomplish a similar effect by using Shannon entropy inequalities in place of explicit encoding. A certain amount of information-theoretic sleight of hand is required to decouple certain random variables to the extent that the Shannon inequalities can be effectively applied. The argument bears some resemblance to the “entropy compression method” discussed in this previous blog post; there may be a way to more explicitly express the argument below in terms of that method. (There is also some kinship with the method of dependent random choice, which is used for instance to establish the Balog-Szemerédi-Gowers lemma, and was also translated into information theoretic language in these unpublished notes of Van Vu and myself.)In the modern theory of additive combinatorics, a large role is played by the Gowers uniformity norms , where , is a finite abelian group, and is a function (one can also consider these norms in finite approximate groups such as instead of finite groups, but we will focus on the group case here for simplicity). These norms can be defined by the formula
where we use the averaging notation
for any non-empty finite set (with denoting the cardinality of ), and is the multiplicative discrete derivative operator
One reason why these norms play an important role is that they control various multilinear averages. We give two sample examples here:
We establish these claims a little later in this post.
In some more recent literature (e.g., this paper of Conlon, Fox, and Zhao), the role of Gowers norms have been replaced by (generalisations) of the cut norm, a concept originating from graph theory. In this blog post, it will be convenient to define these cut norms in the language of probability theory (using boldface to denote random variables).
Definition 2 (Cut norm) Let be independent random variables with ; to avoid minor technicalities we assume that these random variables are discrete and take values in a finite set. Given a random variable of these independent random variables, we define the cut norm
where the supremum ranges over all choices of random variables that are -bounded (thus surely), and such that does not depend on .
If , we abbreviate as .
Strictly speaking, the cut norm is only a cut semi-norm when , but we will abuse notation by referring to it as a norm nevertheless.
Example 3 If is a bipartite graph, and , are independent random variables chosen uniformly from respectively, then
where the supremum ranges over all -bounded functions , . The right hand side is essentially the cut norm of the graph , as defined for instance by Frieze and Kannan.
The cut norm is basically an expectation when :
Example 4 If , we see from definition that
If , one easily checks that
where is the conditional expectation of to the -algebra generated by all the variables other than , i.e., the -algebra generated by . In particular, if are independent random variables drawn uniformly from respectively, then
Here are some basic properties of the cut norm:
Lemma 5 (Basic properties of cut norm) Let be independent discrete random variables, and a function of these variables.
- (i) (Permutation invariance) The cut norm is invariant with respect to permutations of the , or permutations of the .
- (ii) (Conditioning) One has
where on the right-hand side we view, for each realisation of , as a function of the random variables alone, thus the right-hand side may be expanded as
- (iii) (Monotonicity) If , we have
- (iv) (Multiplicative invariances) If is a -bounded function that does not depend on one of the , then
In particular, if we additionally assume , then
- (v) (Cauchy-Schwarz) If , one has
where is a copy of that is independent of and is the random variable
- (vi) (Averaging) If and , where is another random variable independent of , and is a random variable depending on both and , then
Proof: The claims (i), (ii) are clear from expanding out all the definitions. The claim (iii) also easily follows from the definitions (the left-hand side involves a supremum over a more general class of multipliers , while the right-hand side omits the multiplier), as does (iv) (the multiplier can be absorbed into one of the multipliers in the definition of the cut norm). The claim (vi) follows by expanding out the definitions, and observing that all of the terms in the supremum appearing in the left-hand side also appear as terms in the supremum on the right-hand side. It remains to prove (v). By definition, the left-hand side is the supremum over all quantities of the form
where the are -bounded functions of that do not depend on . We average out in the direction (that is, we condition out the variables ), and pull out the factor (which does not depend on ), to write this as
which by Cauchy-Schwarz is bounded by
which can be expanded using the copy as
Expanding
and noting that each is -bounded and independent of for , we obtain the claim.
Now we can relate the cut norm to Gowers uniformity norms:
Lemma 6 Let be a finite abelian group, let be independent random variables uniformly drawn from for some , and let . Then
If is additionally assumed to be -bounded, we have the converse inequalities
Proof: Applying Lemma 5(v) times, we can bound
where are independent copies of that are also independent of . The expression inside the norm can also be written as
so by Example 4 one can write (6) as
which after some change of variables simplifies to
which by Cauchy-Schwarz is bounded by
which one can rearrange as
giving (2). A similar argument bounds
by
which gives (3).
For (4), we can reverse the above steps and expand as
which we can write as
for some -bounded function . This can in turn be expanded as
for some -bounded functions that do not depend on . By Example 4, this can be written as
which by several applications of Theorem 5(iii) and then Theorem 5(iv) can be bounded by
giving (4). A similar argument gives (5).
Now we can prove Proposition 1. We begin with part (i). By permutation we may assume , then by translation we may assume . Replacing by and by , we can write the left-hand side of (1) as
where
is a -bounded function that does not depend on . Taking to be independent random variables drawn uniformly from , the left-hand side of (1) can then be written as
which by Example 4 is bounded in magnitude by
After many applications of Lemma 5(iii), (iv), this is bounded by
By Lemma 5(ii) we may drop the variable, and then the claim follows from Lemma 6.
For part (ii), we replace by and by to write the left-hand side as
the point here is that the first factor does not involve , the second factor does not involve , and the third factor has no quadratic terms in . Letting be independent variables drawn uniformly from , we can use Example 4 to bound this in magnitude by
which by Lemma 5(i),(iii),(iv) is bounded by
and then by Lemma 5(v) we may bound this by
which by Example 4 is
Now the expression inside the expectation is the product of four factors, each of which is or applied to an affine form where depends on and is one of , , , . With probability , the four different values of are distinct, and then by part (i) we have
When they are not distinct, we can instead bound this quantity by . Taking expectations in , we obtain the claim.
The analogue of the inverse theorem for cut norms is the following claim (which I learned from Ben Green):
Lemma 7 (-type inverse theorem) Let be independent random variables drawn from a finite abelian group , and let be -bounded. Then we have
where is the group of homomorphisms is a homomorphism from to , and .
Proof: Suppose first that for some , then by definition
for some -bounded . By Fourier expansion, the left-hand side is also
where . From Plancherel’s theorem we have
hence by Hölder’s inequality one has for some , and hence
Conversely, suppose (7) holds. Then there is such that
which on substitution and Example 4 implies
The term splits into the product of a factor not depending on , and a factor not depending on . Applying Lemma 5(iii), (iv) we conclude that
The claim follows.
The higher order inverse theorems are much less trivial (and the optimal quantitative bounds are not currently known). However, there is a useful degree lowering argument, due to Peluse and Prendiville, that can allow one to lower the order of a uniformity norm in some cases. We give a simple version of this argument here:
Lemma 8 (Degree lowering argument, special case) Let be a finite abelian group, let be a non-empty finite set, and let be a function of the form for some -bounded functions indexed by . Suppose that
for some and . Then one of the following claims hold (with implied constants allowed to depend on ):
- (i) (Degree lowering) one has .
- (ii) (Non-zero frequency) There exist and non-zero such that
There are more sophisticated versions of this argument in which the frequency is “minor arc” rather than “zero frequency”, and then the Gowers norms are localised to suitable large arithmetic progressions; this is implicit in the above-mentioned paper of Peluse and Prendiville.
Proof: One can write
and hence we conclude that
for a set of tuples of density . Applying Lemma 6 and Lemma 7, we see that for each such tuple, there exists such that
where is drawn uniformly from .
Let us adopt the convention that vanishes for not in , then from Lemma 5(ii) we have
where are independent random variables drawn uniformly from and also independent of . By repeated application of Lemma 5(iii) we then have
Expanding out and using Lemma 5(iv) repeatedly we conclude that
From definition of we then have
By Lemma 5(vi), we see that the left-hand side is less than
where is drawn uniformly from , independently of . By repeated application of Lemma 5(i), (v) repeatedly, we conclude that
where are independent copies of that are also independent of , . By Lemma 5(ii) and Example 4 we conclude that
with probability .
The left-hand side can be rewritten as
where is the additive version of , thus
Translating , we can simplify this a little to
If the frequency is ever non-vanishing in the event (9) then conclusion (ii) applies. We conclude that
with probability . In particular, by the pigeonhole principle, there exist such that
with probability . Expanding this out, we obtain a representation of the form
holding with probability , where the are functions that do not depend on the coordinate. From (8) we conclude that
for of the tuples . Thus by Lemma 5(ii)
By repeated application of Lemma 5(iii) we then have
and then by repeated application of Lemma 5(iv)
and then the conclusion (i) follows from Lemma 6.
As an application of degree lowering, we give an inverse theorem for the average in Proposition 1(ii), first established by Bourgain-Chang and later reproved by Peluse (by different methods from those given here):
Proposition 9 Let be a cyclic group of prime order. Suppose that one has -bounded functions such that
for some . Then either , or one has
We remark that a modification of the arguments below also give .
Proof: The left-hand side of (10) can be written as
where is the dual function
By Cauchy-Schwarz one thus has
and hence by Proposition 1, we either have (in which case we are done) or
Writing with , we conclude that either , or that
for some and non-zero . The left-hand side can be rewritten as
where and . We can rewrite this in turn as
which is bounded by
where are independent random variables drawn uniformly from . Applying Lemma 5(v), we conclude that
However, a routine Gauss sum calculation reveals that the left-hand side is for some absolute constant because is non-zero, so that . The only remaining case to consider is when
Repeating the above arguments we then conclude that
and then
The left-hand side can be computed to equal , and the claim follows.
This argument was given for the cyclic group setting, but the argument can also be applied to the integers (see Peluse-Prendiville) and can also be used to establish an analogue over the reals (that was first obtained by Bourgain).
Define the Collatz map on the natural numbers by setting to equal when is odd and when is even, and let denote the forward Collatz orbit of . The notorious Collatz conjecture asserts that for all . Equivalently, if we define the backwards Collatz orbit to be all the natural numbers that encounter in their forward Collatz orbit, then the Collatz conjecture asserts that . As a partial result towards this latter statement, Krasikov and Lagarias in 2003 established the bound
for all and . (This improved upon previous values of obtained by Applegate and Lagarias in 1995, by Applegate and Lagarias in 1995 by a different method, by Wirsching in 1993, by Krasikov in 1989, by Sander in 1990, and some by Crandall in 1978.) This is still the largest value of for which (1) has been established. Of course, the Collatz conjecture would imply that we can take equal to , which is the assertion that a positive density set of natural numbers obeys the Collatz conjecture. This is not yet established, although the results in my previous paper do at least imply that a positive density set of natural numbers iterates to an (explicitly computable) bounded set, so in principle the case of (1) could now be verified by an (enormous) finite computation in which one verifies that every number in this explicit bounded set iterates to . In this post I would like to record a possible alternate route to this problem that depends on the distribution of a certain family of random variables that appeared in my previous paper, that I called Syracuse random variables.
Definition 1 (Syracuse random variables) For any natural number , a Syracuse random variable on the cyclic group is defined as a random variable of the form
where are independent copies of a geometric random variable on the natural numbers with mean , thus
} for . In (2) the arithmetic is performed in the ring .
Thus for instance
and so forth. After reversing the labeling of the , one could also view as the mod reduction of a -adic random variable
The probability density function of the Syracuse random variable can be explicitly computed by a recursive formula (see Lemma 1.12 of my previous paper). For instance, when , is equal to for respectively, while when , is equal to
when respectively.
The relationship of these random variables to the Collatz problem can be explained as follows. Let denote the odd natural numbers, and define the Syracuse map by
where the –valuation is the number of times divides . We can define the forward orbit and backward orbit of the Syracuse map as before. It is not difficult to then see that the Collatz conjecture is equivalent to the assertion , and that the assertion (1) for a given is equivalent to the assertion
for all , where is now understood to range over odd natural numbers. A brief calculation then shows that for any odd natural number and natural number , one has
where the natural numbers are defined by the formula
so in particular
Heuristically, one expects the -valuation of a typical odd number to be approximately distributed according to the geometric distribution , so one therefore expects the residue class to be distributed approximately according to the random variable .
The Syracuse random variables will always avoid multiples of three (this reflects the fact that is never a multiple of three), but attains any non-multiple of three in with positive probability. For any natural number , set
Equivalently, is the greatest quantity for which we have the inequality
for all integers not divisible by three, where is the set of all tuples for which
Thus for instance , , and . On the other hand, since all the probabilities sum to as ranges over the non-multiples of , we have the trivial upper bound
There is also an easy submultiplicativity result:
Proof: Let be an integer not divisible by , then by (4) we have
If we let denote the set of tuples that can be formed from the tuples in by deleting the final component from each tuple, then we have
with an integer not divisible by three. By definition of and a relabeling, we then have
for all . For such tuples we then have
so that . Since
for each , the claim follows.
From this lemma we see that for some absolute constant . Heuristically, we expect the Syracuse random variables to be somewhat approximately equidistributed amongst the multiples of (in Proposition 1.4 of my previous paper I prove a fine scale mixing result that supports this heuristic). As a consequence it is natural to conjecture that . I cannot prove this, but I can show that this conjecture would imply that we can take the exponent in (1), (3) arbitrarily close to one:
Proposition 3 Suppose that (that is to say, as ). Then
as , or equivalently
I prove this proposition below the fold. A variant of the argument shows that for any value of , (1), (3) holds whenever , where is an explicitly computable function with as . In principle, one could then improve the Krasikov-Lagarias result by getting a sufficiently good upper bound on , which is in principle achievable numerically (note for instance that Lemma 2 implies the bound for any , since for any ).
Recent Comments