Tag: discrete geometry

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.

The Schwartz lantern

Conan5 Comments

It’s thanksgiving, let’s have some fun in lantern-making!

This thing called Schwartz lantern initially came up in a talk some years ago, I vaguely remembered it as ‘a cool example where the refining triangle approximation of a smooth surface fail to converge in area’. Anyways, it came up again recently as I was talking to some German postdoc working in ‘discrete differential geometry’. As the example was mentioned, he took a napkin and started folding…and I just realized this lantern can actually be made with a piece of flat paper!

Given a compact, smooth surface (possibly with boundary) embedded in \mathbb{R}^3, we can approximate it by a PL surface with all vertices on the surface and having only triangular faces. (just like what’s done in many computer graphic softwares nowadays).

Question: When the vertices of the faces gets denser and denser and the diameter of triangles converge to 0, does the area of the PL surface converge to the area of the surface?

Ok, to explain why I found this being a quite curious little question, let’s prove a couple of trivial observations:

Trivial fact #1: The sequence of PL surfaces as described above does Hausdorff converge to the smooth surface.

Proof:Since our surface is smooth, as the diameter of the triangles converge to 0, the length of the geodesic between two vertices is roughly the length of the edge in the 1-skeleton of the PL surface. In particular, less than twice its length.

Now by compactness we have a positive injectivity radius, implying that for small enough length c, the diameter (on the surface) of region enclosed by any loop of length most c is controlled by c (say it’s \leq f(c) which converge to 0 as c \rightarrow 0). Now the \mathbb{R}^3 diameter of the region is of course even smaller than its surface diameter.

In conclusion, when all triangles have small diameter \varepsilon (hence all its sides have length at most \varepsilon), the geodesic triangle on the surface has parameter less than 6 \varepsilon . So \mathbb{R}^3 diameter of the geodesic triangle is no more than f(6 \varepsilon). Hence the surface is contained in the f(6\varepsilon)-neighbourhood of the vertex set.

Obviously the PL surface is also contained in this neighbourhood. Hence the Hausdorff distance is at most f(6\varepsilon), which converges to 0.

Trivial fact #2: For curves in \mathbb{R}^2 (in fact, or \mathbb{R}^n), the length converges.

Proof: Well…what can I say…see any undergrad calculus book? (well, all we need is that smooth curves are rectifiable. Of course they are…

So from the above observations, does it kinda smell like the area would converge? (If you know the answer, you should pretend you don’t and nod at this point :-P) Well, the fact is they don’t have to converge! (otherwise why are we making counter-examples here?) Furthermore, this is first discovered by a super-cool dude – Schwartz! He even wrote a paper about it back in 1880.

How can this be possible? You might have already observed that with some simple curvature bounding, we can push the argument for trivial fact #1 to show that area of the curved surface is controlled above by the straight surface, The point being (perhaps to one’s surprise) that the ‘straight surface’ can be a lot LARGER than the curved one!

So the example is a sequence of ‘lanterns’ converging to a standard cylinder (say of height and circumference both equal to 1), i.e. PL surfaces with triangular faces, vertices on the cylinder, with smaller and smaller ‘grids’, and the sum of areas of the triangle blows up to infinity.

As shown above, if we have put N^4 points on the cylinder, N points along the circumference and N^3 in the vertical direction (picture is not to scale); connected to form triangles in the above way.

Now all triangles are isosceles and identical. Doing some middle-school geometry shows that they have base length \geq \frac{1}{2N} and height \geq \frac{1}{4N}\tan^{-1}(\frac{\pi}{2N}) (this calculates the distance between the midpoint of the base to the cylinder surface).

Having 2N^4 triangles means the area A_N of the PL surface is at least N^4 \times \frac{1}{2N} \times \frac{1}{4N}\tan^{-1}(\frac{\pi}{2N}) when N large, \tan^{-1}(\frac{\pi}{2N}) \sim \frac{\pi}{2N} \geq \frac{1}{N}. Hence the A_N \geq \frac{N}{8} blows up to infinity.

Is this pretty cool? This lantern also have an interesting feature that, if we define ‘curvature’ on vertices to be the sum of angles attached to that vertex, (and of course the curvature on the edge between two flat faces shall be 0), then all lanterns have curvature 0 everywhere, just as in the smooth cylinder! i.e. it can be made by folding a single piece of flat paper.

Let’s note that although the triangles are getting uniformly smaller, they do become ‘thinner and thinner’ in the example. In fact this is the only way it can go wrong, i.e. it can be shown that if we further require the triangles to have bounded eccentricity then the area does converge.

Add-on: I actually made the lantern! They are interesting to fold, aesthetically pleasing and even functional! (you’ll see light flaring out in an interesting way)

Trying it out while one thinks about problems is highly amusing and recommended~

All one needs to do is:

Tips on folding:

1. Be sure to make all diagonal lines positive fold and horizontal lines negative.

2. Make the diagonals cross an even number of horizontals or else after you finish all diagonals, you’ll end up with left and right-facing diagonals not crossing on the horizontal (i.e. you’ll need to double the number of horizontals to make it work again)

3. After finishing all lines, it might be hard at first to make the whole thing ‘fold up’. The trick being to make sure all ‘crosses’ are ‘poped-out’ on the whole surface. The final folding process does not work locally!

4. Although theoretically you can take an arbitrarily long strip of paper with unit width to make unit-sized lantern, but in order to not make a million folds and have super-sharp angles between the diagonal and horizontal; I recommend not being too aggressive on the length :-P (square-ish papers are good enough)

Have fun!~

A not-very-good picture of my lantern (larking light bulb…>.<)

A Bosuk-Ulam-kind theorem for simplexes

Conan1 Comment

This little note came out of a lunch discussion with NYU grad student Alfredo Hubard earlier this week. I think the problem-solving process was quite amusing hence worth shearing.

Back in kindergarten, we all learned this theorem called ‘at any given time, there are two opposite places on Earth having exactly the same temperature and air pressure’. Yes that’s the Bosuk-Ulam theorem. I remember at some point I came across a much less famous theorem in some kind of discrete/combinatorial geometry, saying:

Theorem: Any map from a n-dimensional simplex to \mathbb{R}^{n-1} must have a pair of intersecting opposite faces.

Note: each k-dimensional face of the n-dimensional simplex has a unique, well-defined (n-1)-k dimensional opposite face, as shown:

Some examples of maps from the 3-simplex to \mathbb{R}^2:

i.e. in general they can be quite a mess. I think it can be proved by Thurston’s simplex straightening argument. (haven’t checked carefully)

To me this is like Bosuk-Ulam except for instead of considering a large amount of antipodal pairs, we consider only finitely many such pairs. Hence a discrete analoge.

However, one should note that although they are of the same nature, neither follows from the other.

So somehow this theorem came up during the lunch and Alfredo mentioned to me that professor Guth wondered whether the theorem can be proved for mappings from the simplex to lower dimensional simplicial complexes (instead of \mathbb{R}^n). i.e.

Question: Given f: \Delta^{n+1} \rightarrow S where \Delta^{n+1} denote the (n+1)-dimensional simplex and S is a n-dimensional simplicical complex. Then must there be a pair of opposite faces with intersecting image?

So we started to throw out random ideas.

First of all, although only boundary faces of the simplex has non-empty opposite faces (hence can possibly be intersecting pair), it is important that f: \Delta^n \rightarrow S is defined on the solid simplex. (i.e. if one just map the boundary, then we may let S be topologically a sphere and make the map a homeomorphism!) So the moral is, we kind of need to ‘claps’ the simplex to a simply connected lower dimensional thing first, then map it to our S, hence S having non-trivial topology won’t be of much help. Looks almost like the \mathbb{R}^n case, doesn’t it?

Perhaps the image on S can be complicated and has non-trivial topology, but this is merely ‘wrapping’ a contractible, n-dimensional thing around. But wrapping around can only cause more overlapping hence making the faces intersecting more, not less.

The above line of thoughts give an immediate proof in the case when S is a surface and n=2: Lift the map to the universal cover and apply the theorem for \mathbb{R}^2. (It’s a little more tricky when the surface is \mathbb{S}^2 but you can work it out~ the map restricted to \partial \Delta must be of even degree) Note this won’t generalize to higher dimensions (even for manifolds) since universal covers are no longer that similar to \mathbb{R}^n.

So what’s the main difference between complexes and manifolds? well, one can have more than two n dimensional faces attached to the same n-1 dimensional face. I decided to first think of whether Bosuk-Ulam is still true if we further assume that the map extends to the solid ball (as seen above, it is true in the surface case).

After trying to generalize that ‘lifting’ proof for a while, we realized the Bosuk-Ulam does not work for simplicial complexes in all dimensions! For very simple reason, i.e. if we map the n-sphere to \mathbb{R}^n by projecting down, the pre-image of the center point is the only pair of antipodal points that’s mapped together. Hence if instead of \mathbb{R}^n we have three n-simplicies attached along a single (n-1)-simplex (think of it as a piece of \mathbb{R}^n with a vertical simplex attached in the middle):

Now we can still project to that piece of \mathbb{R}^n, with the image of antipodal point lying on the middle (n-1) simplex, all we need to do is to separate this pair while not creating new pairs! But this is easy, just ‘drug’ the upper sheet into the third n-simplex a little bit:

(the region outside of the red neibourhood is unchanged) It’s easy to see that no new antipodal pair is moved together.

So now we turned back to the simplex and realized it’s even easier to argue: project in orthogonal direction to a n-face, originally the only intersecting pair of opposite faces was the vertex and that n-face. Now if we lift the vertex int the third sheet, nothing can intersect~

OK~ perhaps not a useful answer but problem solved!

So far I do not know the answer to the following:

Questions:

1. Is this intersecting faces theorem true for mapping n-simplexes to n-dimensional manifolds?

2. Is the Bosuk-Ulam true if we consider maps from spheres to n-dimensional manifolds which extends to the ball?

The later might be well-known. But so far I can only find a theorem by Conner and Floyd, stating that any map from S^n to a lower dimensional manifold must have a pair of antipodal points mapped together.