Jupyterjones - Productivity Please !!!

That’s the secret of programming.

The Kakeya Problem

Some time ago I (briefly) mentioned that, along with two other students, I was taking a reading course this semester with Dmitriy Bilyk. It hasn’t quite gone in the direction we were initially expecting, but one of our long detours has been an extended sequence of readings around the the Kakeya conjecture. As far as I know, the Kakeya problem (different from the Kakeya conjecture; more on that later) was the first question that fell respectably under the purview of geometric measure theory. So if nothing else, it is interesting from a historical perspective as a question that kickstarted a whole new field of mathematics.

Okay, but what is the Kakeya problem?

As originally posed, it goes like this: given a disk with diameter 1, it is possible to place down a line segment of length 1 into the set, and rotate it (continuously) an entire 180 degrees. But this is not the smallest-area set for which this kind of rotation is possible:

(all pictures in the post are from the Wikipedia page, which is really good)

This set has area $\tau/16$, half that of the circle. So the question naturally becomes: what is the area of the smallest set that allows this kind of rotation?

The answer is known, and it is…

…

zero, basically.

It’s remarkable, but it’s true: you can construct arbitrarily small sets in which you can perform a 180-degree rotation of a line segment! One way to do it goes like this: in the picture above, we reduced the area of the circle by squeezing it until it developed three points. If we keep squeezing to get more points, then the solid “middle” becomes very small, and the tendrils get very thin, so the area keeps decreasing. However, we can still take a line segment and slowly, methodically, shift it back and forth between the set’s pointy bits, parallel-parking style, to eventually get the entire 180 degrees of rotation.

——

You can’t actually get a set with zero area to work. But the reason for that seemed more like a technicality than something actually substantial. So people changed the problem slightly to get rid of those concerns. Now, instead of trying to get a set where you can rotate a line segment through all 180 degrees, you just have to have a set where you can find a line segment in every direction. The difference being that you don’t need to guarantee any smooth way to “move between” these line segments.

Sets that work for the modified problem are often called Kakeya sets (although some people reserve that for the rotation problem and use Besicovitch sets for the modified one). And indeed, there are Kakeya sets which actually have zero area.

The details involved with going from “arbitrarily small” to “actually zero” are considerable, and we won’t get into them here. The following is a simplification (due to Perron) of Besicovitch’s original construction for the “arbitrarily small” case. We take a triangle which clearly has ½ of the directions the needle might possibly take, and split it up into several pieces in such a way that no directions are lost. Then we start to overlap those pieces to get a set (that still has segments in all the same directions) with much smaller area:

We can do this type of construction twice (one triangle “downward-facing” and the other “left-facing”) and then put those two sets together, guarantee that we get all of 180 degrees of directions.

This Besicovitch-Perron construction, itself, only produces sets which are “arbitrarily small”, but was later refined to go all the way to zero. Again, the technicalities involved in closing that gap are (much) more than I want to talk about now. But the fact that these technicalities can be carried out with the Besicovitch-Perron construction is what makes it “better” than the usual constructions for the original Kakeya problem.

——

I should conclude with a few words about the Kakeya conjecture, since I promised them earlier :)

Despite the essentially-solved status of these two classical Kakeya problems, there is at least one big question still left open. It is rather more technical than the original ones, and so doesn’t get a lot of same attention, but I’d like to take a stab at explaining what’s still current research in this sphere of ideas.

Despite the fact that Kakeya sets can be made to be “small” in the sense of measure, we still intuitively want to believe these sets are “big”. There are many ways we can formalize largeness of sets (in $\Bbb R^n$, in particular) but the one that seems to be most interesting for Kakeya things is the notion of Hausdorff dimension. I won’t define the term here, but if you’ve ever heard someone spouting off about fractals, you’ve probably heard the phrase “Fractals have non-integer dimension!”. This is the notion of dimension they’re talking about.

It is known that Kakeya sets in the plane have Hausdorff dimension 2, and that in general a Kakeya set in $n>2$ dimensions has Hausdorff dimension at least $\frac{n}{2}+1$. The proofs of these statements are… difficult, and the general case remains elusive.

One thing more: you can also formulate the Kakeya conjecture in finite fields: in this setting having “dimension $n$” in a vector space over the field $\Bbb F_q$ means that you have a constant times $q^n$ number of points in your set. Wolff proposed this “technicality-free” version in 1999 as a way to study the conjecture for $\Bbb R$. And indeed, a lot of the best ideas for the problem in $\Bbb R$ have come from doing some harmonic analysis on the ideas originally generated for the finite field case. 

But then in 2008 Zeev Dvir went and solved the finite field case completely. Which on one hand is great! But on the other hand, Dvir’s method definitely can’t be finessed to work in $\Bbb R$ so we still have work to do :P

——

Partially I wanted to write about this because it’s cool in its own right, but I must admit that my main motivation is a little more pragmatic. There was a talk at SEICCGTC 2017 which showed a surprising connection between the Kakeya problem and a certain combinatorial game. So if you think these ideas are at all interesting, you may enjoy reading the next two posts in this sequence about that talk.

[ Post 1 ] [ Next ]

Computer simulations that teach themselves to walk.

There are 27 straight lines on a smooth cubic surface (always; for real!)

This talk was given by Theodosios Douvropoulos at our junior colloquium.

I always enjoy myself at Theo’s talks, but he has picked up Vic’s annoying habit of giving talks that are nearly impossible to take good notes on. This talk was at least somewhat elementary, which means that I could at least follow it while being completely unsure of what to write down ;)

——

A cubic surface is a two-dimensional surface in three dimensions which is defined by a cubic polynomial. This statement has to be qualified somewhat if you want to do work with these objects, but for the purpose of listening to a talk, this is all you really need.

The amazing theorem about smooth cubic surfaces was proven by Arthur Cayley in 1849, which is that they contain 27 lines. To be clear, “line” in this context means an actual honest-to-god straight line, and by “contain” we mean that the entire line sits inside the surface, like yes all of it, infinitely far in both directions, without distorting it at all. 

(source)

[ Okay, fine, you have to make some concession here: the field has to be algebraically closed and the line is supposed to be a line over that field. And $\Bbb R$ is not algebraically closed, so a ‘line’ really means a complex line, but that’s not any less amazing because it’s still an honest, straight, line. ]

This theorem is completely unreasonable for three reasons. First of all, the fact that any cubic surface contains any (entire) lines at all is kind of stunning. Second, the fact that the number of lines that it contains is finite is it’s own kind of cray. And finally, every single cubic surface has the SAME NUMBER of lines?? Yes! always; for real!

All of these miracles have justifications, and most of them are kind of technical. Theo spent a considerable amount of time talking about the second one, but after scribbling on my notes for the better part of an hour, I can’t make heads or tails of them. So instead I’m going to talk about blowups.

I mentioned blowups in the fifth post of the sequence on Schubert varieties, and I dealt with it fairly informally there, but Theo suggested a more formal but still fairly intuitive way of understanding blowups at a point. The idea is that we are trying to replace the point with a collection of points, one for each unit tangent vector at the original point. In particular, a point on any smooth surface has a blowup that looks like a line, and hence the blowup in a neighborhood of the point looks like this:

(source)

Here is another amazing fact about cubic surfaces: all of them can be realized as a plane— just an ordinary, flat (complex) 2D plane— which has been blown up at exactly six points. These points have to be “sufficiently generic”; much like in the crescent configuration situation, you need that no two points lie on the same line, and the six points do not all lie on a conic curve (a polynomial of degree 2).

In fact, it’s possible, using this description to very easily recover 21 of the 27 lines. Six of the lines come from the blowups themselves, since points blow up into lines. Another fifteen of them come from the lines between any two locations of blowup. This requires a little bit of work: you can see in the picture that the “horizontal directions” of the blowup are locally honest lines. Although most of these will become distorted near the other blowups, precisely one will not: the height corresponding to the tangent vector pointing directly at the other blowup point.

The remaining six points are can also be understood from this picture: they come from the image of the conic passing through five of the blowup points. I have not seen a convincing elementary reason why this should be true; the standard proof is via a Chow ring computation. If you know anything about Chow rings, you know that I am not about to repeat that computation right here.

This description is nice because it not only tells us how many lines there are, but also it roughly tells us how the lines intersect each other. I say “roughly” because you do have to know a little more about what’s going on with those conics a little more precisely. In particular, it is possible for three lines on a cubic surface to intersect at a single point, but this does not always happen.

I’ll conclude in the same way that Theo did, with a rushed comment about the fact that “27 lines on a cubic” is one part of a collection of relations and conjectured relations that Arnold called the trinities. Some of these trinities are more… shall we say… substantiated than others… but in any case, the whole mess is Laglandsian in scope and unlikely even to be stated rigorously, much less settled, in our lifetimes. But it makes for interesting reading and good fodder for idle speculation :)

Geometry at work: Maxwell, Escher and Einstein

Maxwell’s diagram

from the 1821 “A Philosophical Magazine”, showing the rotative vortexes of electromagnetic forces, represented by hexagons and the inactive spaces between them

The impossible cube

invented in 1958, as an inspiration for his Belvedere litography.

Geometry of space-time

The three dimensions of space and the dimension of time give shape to the fourth, that of space-time.

Big math news! It’s been thirty years since mathematicians last found a convex pentagon that could “tile the plane.” The latest discovery (by Jennifer McLoud-Mann, Casey Mann, and David Von Derau) was published earlier this month. Full story.

Planetary Frequencies.

Co-authored by physicists Ben Tippett* and David Tsang (non-fictional physicists at the fictional Gallifrey Polytechnic Institute and Gallifrey Institute of Technology, respectively), the paper – which you can access free of charge over on arXiv – presents a spacetime geometry that would make retrograde time travel possible. Such a spacetime geometry, write the researchers, would emulate “what a layperson would describe as a time machine“ [x]

Depixellation? Or hallucination?

There’s an application for neural nets called “photo upsampling” which is designed to turn a very low-resolution photo into a higher-res one.

This is an image from a recent paper demonstrating one of these algorithms, called “PULSE: Self-Supervised Photo Upsampling via Latent Space Exploration of Generative Models”

It’s the neural net equivalent of shouting “enhance!” at a computer in a movie - the resulting photo is MUCH higher resolution than the original.

Could this be a privacy concern? Could someone use an algorithm like this to identify someone who’s been blurred out? Fortunately, no. The neural net can’t recover detail that doesn’t exist - all it can do is invent detail.

This becomes more obvious when you downscale a photo, give it to the neural net, and compare its upscaled version to the original.

As it turns out, there are lots of different faces that can be downscaled into that single low-res image, and the neural net’s goal is just to find one of them. Here it has found a match - why are you not satisfied?

And it’s very sensitive to the exact position of the face, as I found out in this horrifying moment below. I verified that yes, if you downscale the upscaled image on the right, you’ll get something that looks very much like the picture in the center. Stand way back from the screen and blur your eyes (basically, make your own eyes produce a lower-resolution image) and the three images below will look more and more alike. So technically the neural net did an accurate job at its task.

A tighter crop improves the image somewhat. Somewhat.

The neural net reconstructs what it’s been rewarded to see, and since it’s been trained to produce human faces, that’s what it will reconstruct. So if I were to feed it an image of a plush giraffe, for example…

Given a pixellated image of anything, it’ll invent a human face to go with it, like some kind of dystopian computer system that sees a suspect’s image everywhere. (Building an algorithm that upscales low-res images to match faces in a police database would be both a horrifying misuse of this technology and not out of character with how law enforcement currently manipulates photos to generate matches.)

However, speaking of what the neural net’s been rewarded to see - shortly after this particular neural net was released, twitter user chicken3gg posted this reconstruction:

Others then did experiments of their own, and many of them, including the authors of the original paper on the algorithm, found that the PULSE algorithm had a noticeable tendency to produce white faces, even if the input image hadn’t been of a white person. As James Vincent wrote in The Verge, “It’s a startling image that illustrates the deep-rooted biases of AI research.”

Biased AIs are a well-documented phenomenon. When its task is to copy human behavior, AI will copy everything it sees, not knowing what parts it would be better not to copy. Or it can learn a skewed version of reality from its training data. Or its task might be set up in a way that rewards - or at the least doesn’t penalize - a biased outcome. Or the very existence of the task itself (like predicting “criminality”) might be the product of bias.

In this case, the AI might have been inadvertently rewarded for reconstructing white faces if its training data (Flickr-Faces-HQ) had a large enough skew toward white faces. Or, as the authors of the PULSE paper pointed out (in response to the conversation around bias), the standard benchmark that AI researchers use for comparing their accuracy at upscaling faces is based on the CelebA HQ dataset, which is 90% white. So even if an AI did a terrible job at upscaling other faces, but an excellent job at upscaling white faces, it could still technically qualify as state-of-the-art. This is definitely a problem.

A related problem is the huge lack of diversity in the field of artificial intelligence. Even an academic project with art as its main application should not have gone all the way to publication before someone noticed that it was hugely biased. Several factors are contributing to the lack of diversity in AI, including anti-Black bias. The repercussions of this striking example of bias, and of the conversations it has sparked, are still being strongly felt in a field that’s long overdue for a reckoning.

Bonus material this week: an ongoing experiment that’s making me question not only what madlibs are, but what even are sentences. Enter your email here for a preview.

My book on AI is out, and, you can now get it any of these several ways! Amazon - Barnes & Noble - Indiebound - Tattered Cover - Powell’s - Boulder Bookstore

How is geometry entangled in the fabric of the Universe?

Geometry can be seen in action in all scales of the Universe, be it astronomical – in the orbital resonance of the planets for example, be it at molecular levels, in how crystals take their perfect structures. But going deeper and deeper into the fabric of the material world, we find that at quantum scale, geometry is a catalyst for many of the laws of quantum-physics and even definitions of reality.

Take for example the research made by Duncan Haldane, John Michael Kosterlitz and David Thouless, the winners of the 2016 Nobel prize in physics. By using geometry and topology they understood how exotic forms of matter take shape based on the effects of the quantum mechanics. Using techniques borrowed from geometry and topology, they studied the changes between states of matter (from plasma to gas, from gas to liquid and from liquid to solid) being able to generate a set of rules that explain different types of properties and behaviors of matter. Furthermore, by coming across a new type of symmetry patterns in quantum states that can influence those behaviors or even create new exotic types of matter, they provided new meaning and chance in using geometry as a study of “the real”.

If the Nobel Prize winners used abstract features of geometry to define physical aspects of matter, more tangible properties of geometry can be used to define other less tangible aspects of reality, like time or causality. In relativity, 3d space and 1d time become a single 4d entity called “space-time”, a dimension perceived through the eye of a space-time traveler. When an infinite number of travelers are brought into the equation, the numbers are adding up fast and, to see how for example, a space-time of a traveler looks for another traveler,  we can use geometric diagrams of these equations. By tracing what a traveler “sees” in the space-time dimension  and assuming that we all see the same speed of light, the intersection points of view between a stationary traveler and a moving one give a hyperbola that represents specific locations of space-time events seen by both travelers, no matter of their reference frame. These intersections represent a single value for the space-time interval, proving that the space-time dimension is dependent of the geometry given by the causality hyperbola.

If the abstract influence of geometry on the dimensions of reality isn’t enough,  take for example one of the most interesting experiments of quantum-physics, the double-split experiment, were wave and particle functions are simultaneously proven to be active in light or matter. When a stream of photons is sent through a slit against a wall, the main expectation is that each photon will strike the wall in a straight line. Instead, the photons are rearranged by a specific type of patterns, called diffraction patterns, a behavior mostly visible for small particles like electrons, neutrons, atoms and small molecules, because of their short wavelength.

Two slits diffraction pattern by a plane wave. Animation by Fu-Kwun Hwang 

The wave-particle duality is a handful, since it is a theory that has worked well in physics but with its meaning or representation never been satisfactorily resolved. Perhaps future experiments that will involve more abstract roles of geometry in quantum fields, like in the case of the Nobel prize winners, will develop new answers to how everything functions at these small scales of matter.

In this direction, Garret Lissi tries to explain how everything works, especially at quantum levels, by uniting all the forces of the Universe, its fibers and particles, into a 8 dimensions geometric structure. He suggests that each dot, or reference, in space-time has a shape, called fibre, attributed to each type of particle. Thus, a separate layer of space is created, parallel to the one we can perceive, given by these shapes and their interactions. Although the theory received also good reviews but also a widespread skepticism, its attempt to describe all known fundamental aspects of physics into one possible theory of everything is laudable. And proving that with laws and theories of geometry is one step closer to a Universal Geometry theory.