mathematics: research – The Accidental Mathematician

Vanishing sums of roots of unity

A root of unity is a complex number $z$ such that $z^n=1$ for some positive integer $n$ . This means that $z=e^{2\pi i k/n}$ for some integer $k$ ; if $k$ is relatively prime to $n$ , we say that $z$ is a primitive $n$ -th root of unity, meaning that $z$ is not a $m$ -th root of unity for any $1\leq m<n$ .

Here’s a question: when can we have

$(1) \ \ z_1+\dots +z_\ell=0$

if $z_1,\dots,z_\ell$ are roots of unity?

This is a little bit vague, in that I did not say what kind of tentative characterization we are looking for. If you were inclined to play devil’s advocate, you could say that equation (1) provides a good enough description. There are, however, less obvious answers that have come in handy in various parts of my research, so let’s look at some of them.

The Coven-Meyerowitz conjecture

The Coven-Meyerowitz conjecture is a tentative characterization of finite sets that tile the integers by translations. It’s also something I have been thinking about, on and off, for more than 2 decades; in the last few years, Itay Londner and I were finally able to make some progress on it. This post will provide a short introduction to the problem, some history, and a little bit of speculation. In a follow-up post (or posts, as there might be more than one), I will say more about our recent work.

The basics. Let $A$ be a set of integers; in this series of posts, we will always assume that $A$ is finite. We will say that $A$ tiles $\mathbb{Z}$ by translations if $\mathbb{Z}$ can be covered by non-overlapping translated copies of $\latex A$. We will use $T$ to denote the set of translations. For example:

The set $A=\{0,1,2\}$ tiles $\mathbb{Z}$ by translations. Indeed, we can just place copies of $A$ next to each other, back to back. A possible translation set is $3\mathbb{Z}=\{... -6, -3, 0, 3, 6, ...\}$ . Note that the translation set need not be unique: for example, $3\mathbb{Z}+1=\{... -5, -2, 1, 4, 7, ...\}$ would also work in this case.
The set $A=\{0,1, 4,5\}$ also tiles $\mathbb{Z}$ by translations. For example, we can add its translate $A+2=\{2,3,6,7\}$ to fill up the discrete interval $\{0,1,2,3,4,5,6,7\}$ , then continue the pattern.
The set $A=\{0,2, 3\}$ does not tile $\mathbb{Z}$ by translations. Once $A$ is in place, there is no way to add a second translate $A+t$ , non-overlapping with $A$ , so that $A+t$ would cover the point 1. (Try it!)

In the above examples, it’s easy to tell whether each set does or does not tile the integers. However, suppose that $A$ is a set of 30 integers between 0 and 100,000. What then? How can we tell whether $A$ tiles the integers or not?

A periodicity argument due to Newman says that the question is decidable, meaning that there is a guaranteed way to get a “yes” or “no” answer in finite time. Specifically, Newman proved the following theorem.

Theorem (Newman). Let $A\subset\mathbb{Z}$ be finite. If $A$ tiles the integers, then every such tiling is periodic with period bounded by $2^{\max(A)-\min(A)}$ .

Here’s the idea of the proof: if $A$ tiles the integers, then it must also tile a discrete interval of length $\max(A)-\min(A)$ . Once it does that, there is only one way to continue the tiling in each direction, and because there are only finitely many configurations of that length available, at some point they have to start repeating themselves, making the tiling periodic. Do this carefully, and you get Newman’s theorem.

Let’s say, then, that $A=\{0,173, 952\}$ . How can we tell whether $A$ tiles the integers? As per the above, we expect the tiling to have period at most $2^{952}$ . We could have a computer check all arrangements of translates of $A$ by shifts between $0$ and $2^{952}$ , and if we do not find a tiling of period bounded by that number, then none exists.

Fortunately, in this case we could also do something more clever than using brute force. Notice that $\{0,173, 952\}$ is a full set of residues modulo $3$ , with $173\equiv 2\mod 3$ and $952\equiv 1\mod 3$ . Therefore $A$ actually tiles the integers with tiling period 3 and the translation set $3\mathbb{Z}$ .

How did I know to check the residues mod $3$ ? Is there a way to do such “smart tricks” more systematically? Also, does this mean that $\{0,173, 951\}$ does not tile the integers?

Let’s see.

The polynomial formulation. Let $A$ tile the integers with period $M$ . This means that the translation set $T$ has period $M$ . so that $T=B\oplus M\mathbb{Z}$ for some finite $B\subset\{0,1,\dots,M-1\}$ . Reducing mod $M$ , we may also assume that $A\subset \{0,1,\dots,M-1\}$ , and write $A\oplus B=\mathbb{Z}_M$ .

(A word on notation: we write $A\oplus B=C$ to say that for every $c\in C$ there is a unique pair $(a,b)\in A\times B$ such that $a+b=c$ . We use $\mathbb{Z}_M$ to denote $\mathbb{Z}$ modulo $M$ . From now on, we will always consider $A,B$ as subsets of $\mathbb{Z}_M$ , with addition mod $M$ .)

We now introduce the polynomial notation. We will use $X$ to denote a variable, and define the mask polynomials

$A(X)=\sum_{a\in A} X^a$ , $\ B(X)=\sum_{b\in B} X^b$ .

(Note that $A(1)=|A|$ , the cardinality of $A$ .) Then the tiling condition $A\oplus B=\mathbb{Z}_M$ is equivalent to

(1) $A(X)B(X)\equiv 1+X+X^2+\dots +X^{M-1} \mod X^{M}-1$ .

This reformulation of the problem is easy (just multiply out the product and compare the exponents), but very useful, because now we can use factorization of polynomials.

Cyclotomic polynomials. The $s$ -th cyclotomic polynomial $\Phi_s$ is the unique irreducible monic polynomial whose roots are the $s$ -th primitive roots of unity. An alternative definition that will be useful to us is based on factorization: for all $M\in\mathbb{N}$ , we have

(2) $X^{M}-1 = \prod_{s|M} \Phi_s(X)$ ,

and this can be used to define all $\Phi_s$ inductively. (Here and below, we always consider only the positive divisors, so that $s\in\mathbb{N}$ .) Start with

$X-1=\Phi_1(X)$ ,

because clearly $X-1$ is irreducible and the only divisor of 1 is 1. Next,

$X^2-1=(X-1)(X+1).$

Since we have already established that $\Phi_1(X)=X-1$ , it follows that $\Phi_2(X)=X+1$ . Similarly,

$X^3-1=(X-1)(X^2+X+1),$

so that $\Phi_3(X)=X^2+X+1$ . This is part of a more general pattern: if $p$ is a prime number, then by the same argument we have $\Phi_p(X)=1+X+X^2+\dots+X^{p-1}$ . Furthermore, if $p$ is prime and $\alpha\in\mathbb{N}$ , we can write

$X^{p^\alpha}-1=(X^{p^{\alpha-1}}-1)(1+X^{p^{\alpha-1}}+\dots+ X^{(p-1)p^{\alpha -1}})$

so that by induction,

(3) $\Phi_{p^\alpha}(X)=1+X^{p^{\alpha-1}}+X^{2p^{\alpha -1}}+\dots+ X^{(p-1)p^{\alpha -1}}=\Phi_p(X^{p^{\alpha-1}}).$

For a composite example, let’s compute $\Phi_6$ :

$X^6-1=(X^3-1)(X^3+1)= \Phi_1(X)\Phi_3(X)(X+1)(X^2-X+1),$

where we used that $X^3-1= \Phi_1(X)\Phi_3(X)$ as above. Also, we already know that $X+1=\Phi_2(X)$ , so that leaves $X^2-X+1$ as $\Phi_6$ .

The Coven-Meyerowitz tiling conditions. Coming back to the tiling equation (1), we see that each $\Phi_s(X)$ with $s|M$ and $s\neq 1$ must divide $A(X)B(X)$ . Since $\Phi_s$ are irreducible (a basic fact from algebra), we get the following.

(4) For all $s|M$ with $s\neq 1$ , the cyclotomic polynomial $\Phi_s$ must divide at least one of $A(X)$ and $B(X)$ (possibly both).

The question of interest is how these cyclotomic divisors are split between $A(X)$ and $B(X)$ . Let $S_A$ be the set of prime powers $p^\alpha$ such that the corresponding cyclotomic polynomial $\Phi_{p^\alpha}(X)$ divides $A(X)$ . In 1998, Coven and Meyerowitz proposed the following tiling conditions.

(T1) $A(1)=\prod_{s\in S_A}\Phi_s(1).$

(T2) If $s_1,\dots,s_m\in S_A$ are powers of distinct primes¹, then $\Phi_{s_1\dots s_m}(X)|A(X).$

Theorem (Coven-Meyerowitz). Let $A\subset\{0,1,2,\dots\}$ be finite.

(i) If $A(X)$ satisfies (T1) and (T2), then $A$ tiles the integers by translations.

(ii) If $A$ tiles the integers by translations, then (T1) holds.

(iii) If $A$ tiles the integers by translations and $|A|$ has at most two distinct prime factors, then (T2) holds.

We do not know whether (T2) must hold for all finite sets that tile the integers. The statement that this must be true has become known as the Coven-Meyerowitz conjecture, even though Coven and Meyerowitz did not actually conjecture this in their paper². This is considered to be the main conjecture in the theory of integer tilings in 1 dimension. The problem turned out to be very difficult and there was very little progress on it until my recent work with Itay Londner – but more on that in future posts.

The (T1) and (T2) conditions may look technical and unintuitive at first – I remember that this was my impression the first time I saw them. So, let’s try to unpack them a bit and figure out what is going on.

It’s relatively easy to see that if $A$ tiles the integers, then (T1) holds. Indeed, suppose that $A\oplus B=\mathbb{Z}_M$ for some $M$ and $B\subset\{0,1,\dots,M-1\}$ . Let $S$ be the set of all prime powers dividing $M$ . By (4), we have $S= S_A\cup S_B$ . Also, by (3) we have $\Phi_{p^\alpha}(1)=p$ . Therefore

$M=\prod_{p^\alpha\in S}p \mid \prod_{p^\alpha\in S_A}p \prod_{p^\alpha\in S_B}p$

$\ \ = \prod_{s\in S_A}\Phi_{s}(1)\prod_{s\in S_B}\Phi_{s}(1) \mid A(1)B(1)=M.$

It follows that we must have equality at each step, and in particular (T1) holds for both $A$ and $B$ . (Additionally, this proves that $S_A$ and $S_B$ are disjoint.) I think of it as a “counting condition”, in the following sense: if $A$ is to tile the integers, its mask polynomial cannot afford to have irreducible divisors $Q(X)$ with $Q(1)\neq 1$ other than prime power cyclotomics, each with multiplicity 1. Otherwise, the tiling condition (1) fails because the cardinalities of $A$ and $B$ cannot match the tiling period.

This is enough to prove that the 3-element set $A=\{0,173, 951\}$ (a modification of the earlier example) does not tile the integers. We have $|A|=3$ . If $A$ did tile the integers, there would be exactly one $\alpha$ such that $\Phi_{3^\alpha}|A$ . Divisibility by prime power cyclotomics has a combinatorial interpretation in terms of equidistribution: if $\Phi_3|A$ , then the elements of $A$ are equidistributed mod 3; if $\Phi_9|A$ , then the elements of $A$ within each residue class mod 3 are equidistributed between the 3 available residue classes mod 9; and so on. In the given example, $173\equiv 2\mod 3$ and $951\equiv 0\mod 3$ , so $A$ is not equidistributed mod 3. It cannot satisfy the higher order equidistribution condition, either, because each residue class mod 3 contains fewer than 3 elements of $A$ . Therefore, no tiling for this $A$ .

Going back to $A=\{0,173, 952\}$ , can we use the Coven-Meyerowitz theorem to decide whether $A$ tiles the integers? Yes. First, observe that $|A|=3$ is a prime number, so that the (T2) condition is vacuous. It therefore suffices to check (T1). (This, and the extension to prime powers, was already known to Newman.) We need to look at divisibility of $A(X)$ by $\Phi_s(X)$ , where $s$ runs over powers of 3. Since $\{0,173, 952\}$ is a full set of residues modulo $3$ as pointed out earlier, we see that $A$ tiles the integers with period 3, this time with less wild guessing and a little bit more of a systematic method.

What about (T2), then? This is a deeper structural property that can be understood in several ways. One interpretation is in terms of equidistribution (possibly within residue classes). Suppose, for example, that $\Phi_2(X)\Phi_3(X)|A(X)$ . Since 2 and 3 are powers of distinct primes, in order for $A$ to satisfy (T2) we must also have $\Phi_6(X)|A(X)$ . This means that

$\Phi_2(X)\Phi_3(X)\Phi_6(X)= 1+X+X^2+\dots+X^5|A(X)$ ,

so that $A$ must be equidistributed mod 6. For example, the set $\{0,3,4,5,7,8\}$ (a complete set of residues mod 6) satisfies (T2) and tiles the integers. On the other hand, if we let $A=\{0,1,2,3,7,8\}$ , then this set is equidistributed mod 2 and mod 3 (hence $\Phi_2(X) \Phi_3(X)|A(X)$ ), but is not equidistributed mod 6. Therefore (T2) fails, and by the Coven-Meyerowitz theorem for 2 prime factors, $A$ does not tile the integers. Of course, for this particular set, we could also see it by inspection (there is no way to cover the numbers 4,5,6 by a translate $A+t$ not overlapping with $A$ ). However, it’s easy to make up examples that look more complicated, but are actually equivalent once you know what to look for. For instance, $\{0,31,62,75, 355, 608\}$ might be less obvious, but has the same set of residues mod 6 as $\{0,1,2,3,7,8\}$ , and does not tile the integers for the same reason.

Another way to understand (T2) that turned out to be rather important in our work is in terms of “standard” tiling complements. Suppose that $A$ satisfies (T1) and (T2). To prove that $A$ must then tile the integers, Coven and Meyerowitz constructed a tiling with period $M=lcm(S_A)$ and an explicit tiling complement $B$ that depends only on the prime power cyclotomic divisors of $A(X)$ . (This happens in the proof of Theorem A in their paper.) Londner and I prove in Section 4.1 of our first paper that having this standard tiling complement is in fact equivalent to (T2). Therefore, to prove that (T2) holds for all finite tiles, it suffices to prove the following: whenever $A$ tiles the integers, it also admits a tiling $A\oplus B^\flat =\mathbb{Z}_M$ , where $M=lcm(S_A)$ and $B^\flat$ is the standard tiling complement for $A$ constructed according to the Coven-Meyerowitz algorithm.

For the sets we considered so far, the standard tiling complements are very simple. If $A$ is a 3-element set with $\Phi_3(X)|A(X)$ , we have $lcm(S_A)=3$ and $B^\flat = \{0\}$ . Similarly, if $A$ is a 6-element set with $\Phi_2(X)\Phi_3(X)\Phi_6(X)|A(X)$ , we have $lcm(S_A)=6$ and $B^\flat = \{0\}$ . Note that the set may have other tiling complements: for instance, if $A=\{0,4,8\}$ , then there is also a tiling of minimal period 12, namely $A\oplus B=\mathbb{Z}_{12}$ with $B=\{0,1,2,3\}$ . (But we still have the standard tiling of period 3.)

In general, we get $B^\flat$ by “filling in” the cyclotomic divisors that might be missing from $A$ . Let’s say for example that $S_A=\{4,9\}$ , and assume also that $A$ satisfies (T2). Since $lcm(S_A)=36$ , we will try to construct a tiling $A\oplus B^\flat=\mathbb{Z}_{36}$ . Note that 2 and 3 are not included in $S_A$ , so that by (4), we must have $\Phi_2(X)\Phi_3(X)|B^\flat(X)$ . If we just try

$B^\flat (X):=\Phi_2(X)\Phi_3(X)=(1+X)(1+X+X^2)$

$=1+X+2X^2+X^3+X^4$ ,

there are two problems with that. First of all, this is not a mask polynomial of a set (because the coefficient of $X^2$ is 2). Second, we need all cyclotomic polynomials $\Phi_s$ with $s|36$ and $s\neq 1$ to divide one of $A(X)$ and $B(X)$ , and our assumptions on $A$ only guarantee that $\Phi_4,\Phi_9,\Phi_{36}$ divide $A(X)$ . (It is possible that $A(X)$ also has some of the other “mixed” cyclotomic divisors, but we do not know that.) So, we will assign preemptively all of the remaining cyclotomic divisors to $B^\flat$ . We can do that by letting

$B^\flat (X):=\Phi_2(X^{9})\Phi_3(X^{4})=(1+X^{9})(1+X^{4}+X^{8})$

$=1+X^{4}+X^{8}+X^{9}+X^{13}+X^{17}$ ,

which fixes both problems. (If you’ve read everything here so far, verifying this is a good exercise.) This produces a tiling complement $B^\flat=\{0,4,8,3,13,17\}$ which is both highly structured (a sumset of the arithmetic progressions $\{0,4,8\}$ and $\{0,9\}$ ) and determined entirely by the prime power cyclotomic divisors of $A(X)$ .

More math next time, but this post would not be complete without some speculation.

Do I think that the conjecture is true? I honestly don’t know, and there are good reasons to expect either outcome. On the negative side, integer tilings can get rather complicated very quickly. There is already a huge jump in difficulty when passing from the 2-prime case to the simplest genuinely 3-prime tilings (the Coven-Meyerowitz paper has 12 pages; my papers with Londner add up to about 200). Beyond that, ~~there be dragons~~ nobody really knows. Wide-sweeping conjectures about tiling and group factorization do not have a good track record of being true without further restrictions, see for example Keller’s conjecture on face sharing in cube tilings, Fuglede’s spectral set conjecture, the conjectures of Hajós and Tijdeman on factorization of finite abelian groups, or, more recently, the periodic tiling conjecture. A general philosophy regarding questions of this type is mentioned in this Quanta Magazine article on the unit conjecture in algebra, which was eventually disproved: “At the time, there was little evidence either way. If anything, there was a philosophical reason to disbelieve the conjectures: As the mathematician Mikhael Gromov is said to have observed, the menagerie of groups is so diverse that any sweeping, universal statement about groups is almost always false, unless there’s some obvious reason why it should be true.” Tilings, too, can be quite diverse and there is a good chance that we do not understand yet the full complexity of the problem, so that situation here may well be similar³.

On the other hand, the Coven-Meyerowitz conjecture does not try to claim anything about tiling and abelian groups in general. It is, specifically, a statement about tilings of the integers, and that makes it a conjecture in number theory at least as much as one in algebra. In number theory, of course, heuristic considerations are quite different. “Serious” conjectures are generally expected, and often confirmed in the end, to be true unless there is some clear reason why this should not be the case.

So, ultimately, I think it will be a tug of war between these two sides of the conjecture. If the resolution turns out to depend on its algebraic aspects, it will likely be negative. If on the other hand the number-theoretic considerations prevail, then the conjecture should be expected to be true, although probably very difficult to prove. Based on my experience (for example, my work with Londner depends very strongly on the fact that we are in a number-theoretic setting), I expect that number theory is more likely to win here. I don’t consider it anywhere close to guaranteed, though, so I’d give it the odds of maybe 55-60%.

If you’d like to tell me what you think, the comments here are closed and will stay closed, but I’m on Twitter and Mastodon (see the sidebar for links), and if that format is not sufficient then I also have a Discord server for math discussions (ask me about getting an invite).

¹ Note that $s_1,\dots,s_m$ should be powers of distinct primes, and not just distinct prime powers. For example, if we assume that $\Phi_2(X)\Phi_3(X)\Phi_4(X)|A(X)$ , then (T2) says that $\Phi_6$ and $\Phi_{12}$ also divide $A(X)$ , but it does not say anything about $\Phi_8$ .

² This is common practice in mathematics. For example, the Kakeya conjecture (a subset of $\mathbb{R}^n$ that contains a unit line segment in every direction must have Hausdorff dimension $n$ ) was named after Sōichi Kakeya, who did not conjecture any such thing. The question that he did ask concerned rotating a needle in the plane, and said nothing about either higher-dimensional spaces or the Hausdorff dimension.

³ For the same reasons, I had not expected the periodic tiling conjecture to be true. I said so when I was interviewed for the Quanta article about it. I was probably not alone in it, either. Instead, Quanta chose to publish a straightforward “mathematicians believed it was true” story and to quote me only on something technical.

Various updates

Polynomial configurations in fractal sets: Kevin Henriot, Malabika Pramanik and I have posted a paper where we prove the following result: if a measure μ on a fractal set E in Rⁿ has Fourier decay with some exponent β, and if it also obeys a ball condition with exponent α close enough to n (depending on β and on the constants in both conditions), then it must contain nontrivial configurations given by certain types of systems of matrices with a polynomial term. This is somewhat similar to my earlier paper with Vincent Chan and Malabika Pramanik, on configurations given by systems of linear forms, but there are significant differences. One is of course the polynomial term: we use stationary phase estimates to control the corresponding part of the “counting form” Λ. (Interestingly, while said stationary estimates apply to functions much more general than polynomials, the polynomial form of the nonlinear term is required for the “continuous” estimates which are based on a number-theoretic argument.) Another is that any rate of Fourier decay β>0 suffices, with the caveat that α must be close enough to n, where “close enough” now depends on both the constants and β. This improvement is due to more efficient use of restriction estimates, and extends to the result with Chan and Pramanik as well as my earlier paper with Pramanik on 3-term arithmetic progressions in fractals. A recent result of Pablo Shmerkin shows that the dependence on constants cannot be removed: he proves, for example, that there exists a 1-dimensional (but of Lebesgue measure 0) Salem set on the line that does not contain a nontrivial 3-term arithmetic progression.

Fractal Knapp examples: Kyle Hambrook and I have been asked on various occasions whether our “Knapp example” for fractal sets on the line could be extended to fractals in higher dimensions. In this paper, we combined our construction (with modifications due to Chen) and the classical Knapp example on the sphere to produce fractal Knapp examples of dimension between n-1 and n in Rⁿ.

My profile for Women in Maths: this was published a while ago, in case anyone here is interested.

It’s been a while since I posted any photos here, so here’s one I took today. There will be more on my Google+ page.

IMG_4547-1

ICM update: talk slides

Since a number of people asked, here are the slides from my ICM talk yesterday. I have also posted them on my preprints page. I believe the talk was recorded and the video will presumably be available from the ICM webpage. Alternatively, you can read my ICM proceedings paper for a longer version.

ICM paper: Harmonic analysis on fractal sets

Somewhat belatedly, here’s the expository paper I wrote for the ICM Proceedings: a short overview of my work with Malabika Pramanik, Vincent Chan and Kyle Hambrook on harmonic analytic estimates for singular measures supported on fractal sets.

The connection between Fourier-analytic properties of measures and geometric characteristics of their supports has long been a major theme in Euclidean harmonic analysis. This includes classic estimates on singular and oscillatory integrals associated with surface measures on manifolds, with ranges of exponents depending on geometric issues such as dimension, smoothness and curvature.

In the last few years, much of my research has focused on developing a similar theory for fractal measures supported on sets of possibly non-integer dimension. This includes the case of ambient dimension 1, where there are no non-trivial lower-dimensional submanifolds but many interesting fractal sets. The common thread running through this work is that, from the point of view of harmonic analysis, “randomness” for fractals is often a useful analogue of curvature for manifolds. Thus, “random” fractals (constructed through partially randomized procedures) tend to behave like curved manifolds such as spheres, whereas fractals exhibiting arithmetic structure (for instance, the middle-thirds Cantor set) behave like flat surfaces. There is a clear connection, at least on the level of ideas if not specific results, to additive combinatorics, where various notions of “randomness” and “arithmetic structure” in sets of integers play a key role.

The paper discusses three specific questions that I have worked on: restriction estimates, differentiation estimates, and Szemeredi-type results. I’ve also mentioned some open problems. At this point, I feel like we’re only started to scratch the surface here; there is much more left to do, for example optimizing the exponents in some of the estimates I’ve mentioned and, perhaps more importantly, figuring out what properties of fractal measures determine such exponents.

Finite configurations in sparse sets

One more paper finished: “Finite configurations in sparse sets,” joint with Vincent Chan and Malabika Pramanik. The paper is available here, and here is the arXiv link.

Very briefly, the question we consider is the following. Let $E \subseteq \mathbb{R}^n$ be a closed set of Hausdorff dimension $\alpha$ . Given a system of $n \times (m-n)$ matrices $B_1, ... ,B_k$ for some $m \geq n$, must $E$ contain a “non-trivial” k-point configuration

$(1)\ \ \ x + B_1 y,\ ...,\ x + B_k y$

for some $x \in \mathbb{R}^n$ and $y \in \mathbb{R}^{m-n}$ ?

In general, the answer is no, even when $\alpha=n$ . For instance, Keleti has constructed 1-dimensional subsets of $\mathbb{R}$ that do not contain a similar copy of any given triple of points $(x,y,z)$ (in fact, his construction can avoid all similar copies of all such triples from a given sequence), as well as 1-dimensional subsets of $\mathbb{R}$ that do not contain any non-trivial “parallelograms” $\{x, x+y, x+x, x+y+z\}$ . In $\mathbb{R}^2$ , given any three distinct points $a,b,c$ , Maga has constructed examples of sets of dimension 2 that do not contain any similar copy of the triangle $abc$ ; he also constructed sets of full dimension in $\mathbb{R}^n$ , for any $n\geq 2$ , that do not contain non-trivial parallelograms.

Additive combinatorics suggests, however, that sets that are “random” in an appropriate sense should he better behaved in that regard. Along these lines, Malabika Pramanik and I proved in an earlier paper that if $E\subset \mathbb{R}$ has dimension close enough to 1, and if it also supports a measure obeying appropriate dimensionality and Fourier decay estimates, then $E$ must contain a non-trivial 3-term arithmetic progression. The same proof applies to any other configuration $x,y,z$ , with the dimension bound depending on the choice of configuration.

This paper gives a multidimensional analogue of that result. We define, via conditions on the matrices $B_j$ , a class of configurations that can be controlled by Fourier-analytic estimates. (Roughly, they must have enough degrees of freedom, and they must be “non-degenerate” in an appropriate sense.) For such $B_j$ , if $E\subset \mathbb{R}^n$ has dimension close enough to $n$ , and if it supports a measure with dimensionality and Fourier decay conditions similar to those in my paper with Pramanik, then $E$ must indeed contain a non-trivial configuration as in (1).

The main new difficulty is dealing with the complicated geometry of the problem. There’s a lot of linear algebra, multiple coordinate systems, multilinear forms, and a lot of estimates on integrals where the integrand decays at different rates in different directions. At one point, we were actually using a partition of unity similar to those I remembered from my work in multiparticle scattering theory a very long time ago. That didn’t make it into the final version, though – we found a better way.

I won’t try to state the conditions on $B_j$ here – they’re somewhat complicated and you’ll have to download the paper for that – but I’ll mention a few special cases of our theorem.

Triangles in $\mathbb{R}^2$ . Let $a,b,c$ be three distinct points in the plane. Suppose that $E\subset\mathbb{R}^2$ satisfies the assumptions of our main theorem. Then $E$ must contain three distinct points $x,y,z$ such that the triangle $\triangle xyz$ is a similar (possibly rotated) copy of the triangle $\triangle abc$ .
Colinear triples in $\mathbb{R}^n$ . Let $a,b,c$ be three distinct colinear points in $\mathbb{R}^n$ . Assume that $E\subset\mathbb{R}^n$ satisfies the assumptions of our main theorem. Then $E$ must contain three distinct points $x,y,z$ that form a similar image of the triple $a,b,c$ .
Parallelograms in $\mathbb{R}^n$ . Assume that $E\subset\mathbb{R}^n$ satisfies the assumptions of our main theorem. Then $E$ contains a parallelogram $\{x,x+y,x+z,x+y+z\}$ , where the four points are all distinct.

Visibility of unrectifiable planar sets

Matt Bond, Josh Zahl and I have just completed a new paper “Quantitative visibility estimates for unrectifiable sets in the plane,” now available on the arXiv. This post is an informal introduction to the paper; for more details, you will need to download the actual article.

There are several questions known as “visibility problems”, and the one we address is the following. We are given a compact set $E$ in the plane, and a point $a$ not in $E$ . Define $P_a$ to be the radial projection from $a$ :

$P_a(x) = \frac{x-a}{|x-a|}$

Then $P_a(E)$ is the set of angles at which $E$ is visible from $a$ . Our “visibility problem” is then to estimate the size of $|P_a(E)|$ , or equivalently, the proportion of the part of the field of vision that $E$ takes up for an observer situated at $a$ .

One class of sets that we will study is 1-dimensional unrectifiable self-similar sets. A good example to keep in mind is the “4-corner set,” constructed via a Cantor iteration as follows. Start with a square, divide in into 16 congruent squares, and keep the 4 small squares at the corners, discarding the rest. Repeat the same procedure for each of the 4 small surviving squares, then iterate the construction. The first and second stage of the iteration are shown below.

We will use $K_n$ for the $n$ -th iteration of this set, and $K$ for the Cantor set $K = \bigcap_{n=1}^\infty K_n$ .

What can we say about the visibility of $K$ from points $a$ in the plane? We will assume that $a \notin K$ , so as to avoid trivial debates over whether a point is visible from itself. We will be asking this question in terms of the size of $P_a(K)$ , as expressed in terms of its Lebesgue measure and/or Hausdorff dimension.

Continue reading “Visibility of unrectifiable planar sets”

An expository paper on the Favard length problem

In case there’s anyone here who’s interested in the Favard length problem, I have just finished an expository paper written for the proceedings of the 2012 Abel Symposium. There has been a good deal recent progress on the subject in recent years, starting with this 2008 paper by Nazarov, Peres and Volberg, through my paper with Zhai, two papers by Bond and Volberg, and most recently my paper with Bond and Volberg. This exposition focuses especially on the number-theoretic aspects of the question for rational product sets, developed mostly in the BLV paper, although some of it goes back to the earlier papers. You can think of it as BLV-lite if you wish.

I have tried to keep the exposition as simple as possible, omitting many of the technicalities and focusing on examples where we can deal with just one number-theoretic issue at a time (as opposed to BLV, where we must combine the different methods together). I’ve also added a good deal of discussion and commentary. This makes the paper a bit more verbose than what I’m used to, but most of this was written in response to questions that I have actually been asked, so I hope that this will be a useful companion paper to BLV and the other references. Also, I did have a deadline for this, so a couple of things (notably the “Poisson lemma” in Section 3.1) got short shrift, and I probably would have found a few more typos and other such if I’d had more time to chase them. Oh well.

There are a couple of new things at the end of the paper. One is Conjecture 4.6. Matt Bond and I came up with this while trying to figure out whether the assumption on the cardinalities of product sets in BLV can be dropped. If the conjecture turns out to be true, than we can indeed drop that assumption. We have some supporting evidence for various special cases, but we don’t know how to prove it in general.

The second part that has not been published previously concerns “random 4-corner sets”. Peres and Solomyak (Pacific J. Math. 2002) proved that for a randomized version of the 4-corner set construction, the expected Favard length asymptotics is in fact C/n. This is a very nice geometric argument, but I found the original proof quite hard to read, so I reworked and simplified it some time ago. This is included here in Section 5.

The paper can be downloaded here. It will also be posted on the arXiv, if I can figure out how to post LATEX files with pictures.

A Knapp example for Salem sets on the line

The restriction phenomenon in harmonic analysis is best known for surface measures on manifolds. A classical example is the unit sphere, where on the one hand we have the Stein-Tomas restriction theorem for $L^2$ densities on the sphere, and on the other hand, Stein’s restriction conjecture for $L^\infty$ densities remains open. (Partial intermediate results are also available, but that is a longer story that will have to wait for another time.)

However, restriction estimates can also be proved for fractal sets. Continue reading “A Knapp example for Salem sets on the line”

Buffon’s needles: a very short expository note

One of the things I have been working on in the last few years is the Favard length problem. The question is to estimate the average length of a 1-dimensional projection of (a finite iteration of) a 1-dimensional self-similar Cantor set in the plane. My work with Zhai, and especially with Bond and Volberg, has pointed to connections with classical questions in number theory, including tilings of the integers, diophantine approximation of logarithms of algebraic numbers, and vanishing sums of roots of unity.

If you would like to find out a little bit more about this, but don’t necessarily feel like reading long technical papers that rely on several other long technical papers, then this very short expository note (3 pages plus short bibliography) might be for you. It was written for the CMS Notes and has about the length they require. I found myself wanting to make it longer, if only to include more references to the history and context of the problem. (I never even mentioned Comte de Buffon.) I might write a more substantial expository paper when I have the time.