Tag: projection

Sumsets, in discrete and continuous settings

Conan4 Comments

In the past few years, there are 137 papers with the term ‘sumset’ in its title; and 50 more with ‘sum-set’. Ok the above statement was stolen from a talk I happen to be sitting in, by Noga Alon.

As usual, in the middle of the talk I got carried away by some ‘trivial facts’ he wrote down which are only slightly related to the main content. So I thought about that for during the rest of the talk (and also a little bit afterwards).

This time the curious point pops up when he was motivating why people should be studying chromatic number of random Cayley graphs by its application to sumsets.

Definition: In a vector space X, a sumset S \subseteq X is a set that can be represented as the Minkowski sum of another set with itself. i.e. S = A+A where A+A = \{ a_1+a_2 \ | \ a_1, a_2 \in A \}.

It was mentioned that given a large p, if we look at sets in \mathbb{Z}_p, then all sets with large cardinality must be sumsets.

This fact is first published by Ben Green who also raised the natural question:

Question: What’s the lower bound M(p) such that all subsets S \subseteq \mathbb{Z}_p with |S| > M(p) must be a sumset?

Let’s first see why all sets of large cardinality must be sumsets: Well as we all know \mathbb{Z}_p = \mathbb{Z}_p + \mathbb{Z}_p (can also be expressed as many other sums) is a sumset. Hence the first non-trivial case is \mathbb{Z}_p \backslash \{x\}:

The way I think of sumsets is that they are projections of product sets in the angle 3/4 \pi:

Hence our goal is to make up a set S_x such that the projection, after mod p, is everything except for the point x. Well, this isn’t too hard, first note the image of the ‘interval’ \{ x+1, x+2, \cdots, p+x-1 \} after mod p is exactly the set we wanted. Now we just need to make A \times A project to the interval! A = \{ x/2 +1, x/2 + 2, \cdots (p+x)/2 -1 \} will do. (Here by C/2 we meant that it’s the integer C/2 when C is even and (C+p)/2 when it’s odd.

Note that since x \in \mathbb{Z}_p, A + A is actually a square in \{ 0, 1, \cdots, p-1 \}^2 and only “warped” in mod p after we project it to \{ 0, 1, \cdots, 2p-2 \}.

So we just showed all sets with one missing element is a sumset~ Now let’s move to sets of size p-2…(Don’t worry, I’m not going on to 3 and the length of this post will be finite :-P)

In contrast to the above argument which actually works in the continuous setting and shows the Lie group S^1 missing any interval is a sumset, this time we actually need to use the fact that our space is discrete and finite.

Note first that the property of being a sumset is invariant under scaling and translating by an integer. Indeed,

n\cdot S = \{ ns \ | \ s \in S \}

= \{n(a_1+a_2) \ | \ a_1, a_2 \in A\} = n \cdot A + n \cdot A

and of course S+t = (A+t/2) + (A+t/2).

Now no matter which two points a,b we delete, i.e. S = \mathbb{Z}_p \backslash \{a, b \}, we may let S' = (b-a)^{-1} \cdot (S-a). We have S' = \mathbb{Z}_p \backslash \{0, 1\}, which is the projection of the square I^2 = \{ 1,2, \cdots, (p-1)/2 \}^2.

Hence S = [(b-a) \cdot I + a/2] + [(b-a) \cdot I + a/2] is a sumset.

After playing around with the torus for a little bit, I believe in the continue case we can still write S^1 deleting two (small) intervals as a sumset A+A where A is a union of no more than 4 intervals. There are quite a few cases involved concerning the spacing between small intervals, hence I’ll just draw an example:

(By the way, this is about as far as I got daydreaming during the lecture, the rest came from the sources I looked up afterwards.)

Unfortunately since the scaling and translating gived only two degrees of freedom, the above argument fails when considering sets missing three points. (Playing with torus as I first tried, however, might still work)

Back to our question, so now we know at least M_p < p-2 the natural thing to study is of course how does it grow with p. Recall that we denoted M_p = p - f(p), hence the problem is equivalent to giving asymptotic lower bounds for f(p).

So this is quite curious, what do you think? Is f(p) just a counstant? (such as 2, or 3?) Or is it always more than a fixed proportion of \mathbb{Z}_p? (say any set containing 99% of the elements must be a sumset?) Or something in-between?

As one might have expected, f(p) is more than a constant,

Theorem: (Green) f(p) \geq \frac{1}{9} \log_2(p).

It’s also not as large as a fixed percentage:

Theorem: (Gowers-Green) f(p) \leq C \cdot p^2/3 \log(p)

So it’s something ‘in-between’. Interesting…So what is this number? This is an open question in general, by applying methods of Cayley graphs and their spectrums, the speaker (of the talk) was able to improve the above bounds (in this other paper):

Theorem: (Alon) c \cdot \sqrt{\frac{p}{\log{p}}} \leq f(p) \leq C \cdot \frac{ p^2/3}{ \log(p)^{1/3}}

However one should expect that

Conjecture: (Green) f(p) \sim p^{1/2+O(1)}.

Having knowing absolutely nothing about the subject (or combinatorics in general), my first reaction about this is that perhaps, if we look at \mathbb{Z}_p where p is roughly N^2, let S be the set missing N equally spaced points, now if we want to write S as a sumset that’s like finding a product A \times A \subseteq \mathbb{T}^2 that misses all N diagonal circles and have at least N points in each thin strip to ‘block’ every diagonal circle in the strip.

I think this set looks (by the same philosophy as when we play around with the two intervals on the tori case) fairly hard to express as a sum. i.e. when we are exactly in \mathbb{Z}_{N^2}, we can probably ‘just’ do it by choosing one representative from each mod N class and place them in the N strips. But looks as if the ‘resolution’ is any lower, (i.e. p is a little smaller and we still have about N equally spaced holes), we would not have enough freedom to place the points.

Anyways, that last remark might be completely nonsense~ The conjecture is interesting, tho.

On Uryson widths

ConanLeave a comment

This is a note on parts of Gromov’s paper ‘width and related invariants of Riemannian manifolds’ (1988).

For a compact subset C of \mathbb{R}^n, we define the k-codimensional width (or simply k-width) to be the smallest possible number w where there exists a k-dimensional affine subspace P_k \subseteq \mathbb{R}^n s.t. all points of C is no more than w away from P_k.

i.e.

\displaystyle{W}_k(C) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p\in C} \mbox{dist}(p, P_k)
where \mbox{dist}(p, P_k) is the length of the orthogonal segment from p to P_k.

It’s easy to see that, for any C,

\mathcal{W}_0(C) \geq \mathcal{W}_1(C) \geq \cdots \geq \mathcal{W}_n(C) = 0.

At the first glance it may seems that \mathcal{W}_0(C) = \frac{\mbox{diam}(C)}{2}. However it is not the case since for example the equilateral triangle of side length 1 in \mathbb{R}^2 has diameter 1 but 0-width \frac{1}{\sqrt{3}}. In fact, by a theorem of Jung, this is indeed the optimum case, i.e. we have:

\frac{1}{2}\mbox{diam}(C) \leq \mathcal{W}_0(C) \leq \sqrt{\frac{n}{2(n+1)}}\mbox{diam}(C)

At this point one might wonder (at least I did), if we want to invent a notion that captures the ‘diameter’ after we ‘forget the longest k-dimensions’, a more direct way seem to be taking the smallest possible number w' where there is an orthogonal projection of C onto a k dimensional subspace P_k where any point p \in P_k has pre-image with diameter \leq w'.

i.e.

\displaystyle \widetilde{\mathcal{W}_k}(X) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p \in P_k} \mbox{diam}(\pi^{-1}_{P_k}(p))

Now we easily have \mbox{diam}(C) = \widetilde{\mathcal{W}_0}(C) \geq \widetilde{\mathcal{W}_1}(C) \geq \cdots \geq \widetilde{\mathcal{W}_n}(C) = 0.

However, the disadvantage of this notion is, for example, there is no reason for a semicircle arc to have 1-width 0 but a three-quarters circular arc having positive 1-width.

Since we are measuring how far is the set from being linear, taking convex hull should not make the set ‘wider’ \widetilde{\mathcal{W}_k}, unlike \widetilde{\mathcal{W}_k} is not invariant under taking convex hulls. Note that for convex sets we do have

\frac{1}{2}\widetilde{\mathcal{W}_k}(C) \leq \mathcal{W}_k(C) \leq \sqrt{\frac{n-k}{2(n-k+1)}}\widetilde{\mathcal{W}_k}(C)

\mathcal{W}_k(C) = 0 iff C is contained in a k-plane.

We now generalize this notion to general metric spaces:

Definition: The Uryson k-width of a compact metric space M is the smallest number w where there exists k dimensional topological space X and a continuous map \pi: M \rightarrow X where any point x \in X has pre-image with diameter \leq w.

i.e. \displaystyle UW_k(M) = \inf \{ \ \sup_{x \in X} \mbox{diam}(\pi^{-1}(x)) \ |

\dim{X} = k, \pi:M \rightarrow X \ \mbox{is continuous} \}

Note: Here dimension is the usual covering dimension for topological spaces: i.e. a topological space X is n dimensional if any finite cover of X has a finite refinement s.t. no point of X is contained in more than n_1 sets in the cover and n is the smallest number with this property.

For compact subsets C of \mathbb{R}^n with induced metric, we obviously we have UW_k(C) \leq \widetilde{\mathcal{W}_k}(C) since the pair (P_k, \pi_{p_k}) is clearly among the pairs we are minimizing over.

Speaking of topological dimensions, one of the classical results is the following:

Lebesgue’s lemma: Let M=[0,1]^n be the solid n-dimensional cube, then for any topological space X with \dim(X)<n and any continuous map p: M \rightarrow X, we have image of at least one pair of opposite (n-1)-faces intersect.

Since the conclusion is purely topological, this applies equally well to rectangles. i.e. for M = [0, L_1] \times [0, L_2] \times \cdots \times [0, L_n], L_1 \geq L_2 \geq \cdots \geq L_n, we have UW_{n-1}(M) \geq L_n; furthermore, UW_k(M) \geq L_{k+1} for all k.

(If the later statement does not hold, we write M as M_1 \times M_2, M_1 being the product of the first (k+1) coordinates. Now UW_k(M) \geq UW_k(M_1) \geq L_{k+1}).

In light of the earlier post about minimax inequality, we should note that if we restrict X to be a homeomorphic copy of \mathbb{R}^k then the notion is the same as the minimax length of fibres. In particular as proved in the post the minimax length of the unit disc to \mathbb{R} is 2.

Exercise: Check that for the unit 2-disk, UW_1(D^2) = \sqrt{3}, i.e. the optimum is obtained by contracting the disc onto a triod.

Hence it can indeed be strictly smaller than merely taking \mathbb{R}^k as the targeting space, even for simply connected sets. This gives a better measurement of ‘width’ in the sense that, for example, the \varepsilon neighborhood of a tree will have 1-width about 2 \varepsilon.

Hausdorff dimension of projections

ConanLeave a comment

A few days ago, professor Wilkinson asked me the following question on google talk (while I was in Toronto):

“Say that a set in \mathbb{R}^n is a k-zero set for some integer k<n if for every k-dimensional subspace P, saturating the set X by planes parallel to P yields a set of n-dimensional Lebesgue measure zero. How big can a k-zero set be?”

On the spot my guess was that the Hausdorff dimension of the set is at most n-k. In deed this is the case:

First let’s note that n-dimensional Lebesgue measure of the P-saturated set is 0 iff the n-k dimensional Lebesgue measure of the projection of our set to the n-k subspace orthogonal to P is 0.

Hence the question can be reformulated as: If a set E \subseteq \mathbb{R}^n has all n-k dimensional projection being n-k zero sets, how big can the set be?

Looking this up in the book ‘The Geometry of Fractal Sets’ by Falconer, indeed it’s a theorem:

Theorem: Let E \subseteq \mathbb{R}^n compact, \dim(E) = s (Hausdorff dimension), let G_{n,k} be the Garssmann manifold consisting of all k-dimensional subspaces of \mathbb{R}^n, then
a) If s \leq k, \dim(\mbox{Proj}_\Pi E) = s for almost all \Pi \in G_{n,k}

b) If s > k, \mbox{Proj}_\Pi E has positive k-dimensional Lebesgue measure for almost all \Pi \in G_{n,k}.

In our case, we have some set with all n-k-dimensional projection having measure 0, hence the set definitely does not satisfy b), i.e. it has dimensional at most n-k. Furthermore, a) also gives that if we have a uniform bound on the dimension of almost all projections, this is also a bound on the dimension of our original set.

This is strict as we can easily find sets that’s n-k dimensional and have all such projections measure 0. For example, take an n-k subspace and take a full-dimension measure 0 Cantor set on the subspace, the set will have all projections having measure 0.

Also, since the Hausdorff dimension of any projection can’t exceed the Hausdorff dimension of the original set, a set with one projection having positive n-k measure implies the dimension of the original set is \geq n-k.

Question 2: If one saturate a k-zero set by any smooth foliations with k-dimensional leaves, do we still get a set of Lebesgue measure 0?

We answer the question in the affective.

Given foliation \mathcal{F} of \mathbb{R}^n and k-zero set E. For any point p \in E, there exists a small neighborhood in which the foliation is diffeomorphic to the subspace foliation of the Euclidean space. i.e. there exists f from a neighborhood U of p to (-\epsilon, \epsilon)^n where the leaves of \mathcal{F} are sent to \{\bar{q}\} \times (-\epsilon, \epsilon)^k, \bar{q} \in (-\epsilon, \epsilon)^{n-k}.

By restricting f to a small neighborhood (for example, by taking \epsilon to be half of the origional \epsilon), we may assume that f is bi-Lipschitz. Hence the measure of the \mathcal{F}-saturated set inside U of U \cap E is the same as f(U \cap E) saturated by parallel k-subspaces inside (-\epsilon, \epsilon)^n. Dimension of f(E) is the same as dimension of E which is \leq n-k, if the inequality is strict, then all projections of f(E) onto n-k dimensional subspaces has measure 0 i.e. the saturated set by k-planes has n dimensional measure 0.

…to be continued