"The Dream of a Ridiculous Man"

And yet it's so simple: in one day, in one hour - it could all be set up at once! The main thing is -- love others as yourself, that's the main thing, and it's everything, there's no need for anything else at all: it will immediately be discovered how to set things up. And yet this is merely an old truth, repeated and read a billion times, but still it has never taken root! "The consciousness of life is higher than life, the knowledge of the laws of happiness is higher than happiness" -- that is what must be fought! And I will. If only everyone wants it, everything can be set up at once.
And I found that little girl . . . And I'll go! I'll go!

-- The Dream of a Ridiculous Man, F.M. Dostoyevski

I have been working on some book typesetting, and a few things are almost ready to be shared. This is not one of them though; at least not the English translation.

Understanding convex polytopes (III)

This entry marks the end of my short series of posts regarding convex polytopes and graph-associahedra. I've had lots of fun and learned a lot during this month of research. Here follows a summary of the conclusions of our work.

Understanding the polytope made from $\text{Cycle}_n$ in a constructive manner proved to be harder than anticipated, and we summed up our work in this area with a conjecture relating the $\mathcal{B}$-trees of the cycle on $n+1$ vertices with the lattice paths on the $n \times n$ grid. Recall that the $\mathcal{B}$-trees of the cycle are just binary trees with an extra root at $n+1$, with a certain $\pmod{n+1}$ shift applied to the labels. We can define an equivalence relation based on this operation, and say that two trees $T_1$ and $T_2$ are congruent if they are generated from the same binary tree (with an extra root) $T$. Let $[T]$ denote the equivalence class of $n+1$ trees generated by a canonical binary tree $T$ and the shifting operation. We proceed to define the other side of the relation, lattice paths.

There is a direct construction of lattice paths from $(0,0)$ to $(n,n)$ on the $n \times n$ grid, in particular Dyck paths (those which do not cross the diagonal), from binary trees by expressing a binary tree as a balanced parenthesis sequence. We need to define a parallel of descent for lattice paths, for that is the center of our conjecture. Let $\text{peaks}(P)$ be the number of left-peaks of a lattice path; from the parenthesized construction, a left-peak in the Dyck path is equivalent to a descent in the binary tree. Next, we need to find an operation which serves as parallel for our label shifting on trees. There is a cool operation on Dyck paths (defined by Chen in [1]) which generates a set of $n+1$ lattice paths, and so we define again an equivalence relation based on this operation, with $[P]$ denoting the equivalence class of lattice paths generated from a Dyck path $P$. For distinct $P$ and $P'$, we can show that $[P] \cap [P'] = \varnothing$, and equivalently for our canonical binary trees.

As stated, there is a map $\Phi : \text{binary trees} \rightarrow \text{Dyck paths}$, and we conjecture that the descent generating function of the equivalence class $[T]$ is equal to the descent generating function of the equivalence class $[\Phi(T)]$:

$$\sum_{T' \in [T]} x^{\text{des}(T')} = \sum_{P' \in [\Phi(T)]} x^{\text{peaks}(P')}$$

We verified the conjecture for $n$ up to 13.

On the other hand, we found a combinatorial interpretation for the $\gamma$-polynomial of the cyclohedron. Following the approach of Posntnikov et al. in [2], we defined yet another delicate operation on lattice paths, allowing us to arrive to the desired $\gamma(x) = \sum_{r=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor}\binom{n}{r,r,n-2r} x^r$ in a nice combinatorial way, in contrast to the previous work based on hyper-geometric series manipulations on the $h$-polynomial.

In conclusion, I am extremely happy of the work we've done, considering my very limited exposure to advanced mathematics (and even less to research level mathematics!). I enjoyed the research experience, and the constant unknown factor was such a motivator to keep me going; what's this? What if I do that? Are we doing the right thing? Is there another point of view? I am certainly convinced to pursue mathematics for as long as I can.

References

[1] Chen, Y. M. (2008), The Chung–Feller theorem revisited. Discrete Mathematics, 308(7), 1328-1329.
[2] Postnikov, A., Reiner, V., & Williams, L. (2008). Faces of generalized permutohedra. Doc. Math, 13(207-273), 51.

Understanding convex polytopes (II)

Second post about my summer research. This is a jump from the last one, but I need to clear my head. Here it goes.

After about two weeks of lots of reading, I've begun my independent inquiries. This will (and has to, to some extent) sound like pure brain-storming, incoherent babbling; but I need to keep track of where I want to get to.

We know (cite here) that the $h$-vector of a nestohedron $P_{\mathcal{B}}$ can be described in as the generating function of the descent number of its $\mathcal{B}$-trees:

$$h_{P_{\mathcal{B}}}(t) = \sum_T t^{\text{des}(T)}.$$

Given how there exists a bijection (cite here) between the vertices of $P_{\mathcal{B}}$, the $\mathcal{B}$-permutations and the $\mathcal{B}$-trees, it is clear that to understand the combinatorial structure of a nestohedra, we must understand the structure of its underlying building set.

In the case of graph-associahedra, I want to find results about their $h$- and $\gamma$-polynomials in constructive and intuitive ways. I've started working on finding that information about the graph-associahedra $P_{\mathcal{B}(\text{Cycle}_n)}$ of the cycle graph on $n$ vertices.

Let's suppose that we fully know what's the combinatorial structure of $P_{\mathcal{B}(\text{Path}_n)}$ (we do), and that we don't know anything about $P_{\mathcal{B}(\text{Cycle}_n)}$ (we do as well, but bare with me). If you consider the graph $\text{Path}_{(n-1)}$ with two added edges, from endpoints $1$ and $(n-1)$ to a new vertex $r$, you've essentially pictured $\text{Cycle}_n$ in your head. The idea of describing the graph-associahedra of the cycle graph in terms of the simpler path graph is cool. In fact, the idea of describing the graph-associahedra of any graph by `gluing' smaller, more understandable (or more understood) graphs is extremely attractive and logical to me. It makes sense to reuse simple constructs to provide descriptions of more complex ideas; but of course, it isn't easy. I don't even know if I'll be able to finish the example presented here, but it is a good warm-up exercise for this poor soul's first attempt at providing novel insight, no matter how insignificant.

I was feeling like finishing the post here, but i realize i haven't actually delved into the complicated stuff, and i want to reach the point where i can't go further, and observe then where's the weakness, where's the limitation.

We can define the set of $\mathcal{B}$-trees for $\text{Cycle}_n$ as follows: for each $r \in [n]$, construct the set of trees of $\text{Path}_{(n-1)}$ such that the label $i$ of every vertex of a tree $T$ is replaced by $i' = i + r \pmod{n}$. Join the root of $T$ to our newly defined root $r$, to get $T'$. Notice then that the forest of trees constructed from $\mathcal{B}(\text{Cycle}_n)$ has $n \cdot C_{(n-1)}$ trees ($C_n$ is the $n$th Catalan number; it is known that there are $C_n$ trees for the $n$-path).

So, to find $h_{P_{\mathcal{B}(\text{Cycle}_n)}}(t)$, we must count the descent numbers of the $n$ copies of the $\mathcal{B}$-forest of $\text{Path}_{(n-1)}$ with its labels shifted $r \in [n]$ modulo $n$. I hope you can see that the delicate part is the shifting of labels: if $n=5$ and in some tree from $\text{Path}_4$ we had a descent $4 \leftarrow 5$, when we adjoin the new root $r=1$, all indices are shifted and the descent becomes $5 \leftarrow 1$, which is not a descent anymore. Chaos! We must understand how does that shifting affect the descent number of the trees of $\text{Cycle}_n$. Here's where i'm at.

A small observation, to close this post. It may be obvious, but it has just occurred to me and i haven't come up with a proof from the top of my head: if you pick a tree $T$ from the forest of $\mathcal{B}(\text{Cycle}_n)$-trees, and exchange the root with its unique child, the resulting tree $T'$ is also a tree in the forest. If you apply the operation twice, you obviously go back to $T$. If closure were true, this would define an equivalence relation which halves the size of the forest. Postnikov et al. use a `similar' (this deserves triple quotes) operation to fully describe the graph-associahedra of the path graph. I may try to do something similar? But i realize that I'm not using what i know about the descents of the trees of the path graph itself! Back to work.

Understanding convex polytopes (I)

This summer, i'm working in an intense month-long research program about discrete geometry (a.k.a. combinatorial geometry). To keep track of what i do, what i learn and what i don't, i'll be writing (hopefully) regular posts regarding the work i do through the day. That should help me a ton, and hopefully someone out there as well?

Consider a set of points $P \subset \mathbb{R}^n$. We say that $P$ is convex if for any $x,y \in P$, the segment $[x,y]$ is contained in $P$. An intersection of convex sets is convex, so we define the convex hull of $P$ as the smallest convex set that contains $P$:

$$\text{ConvexHull}(P) := \bigcap \{P' \subset \mathbb{R}^n : P \subset P', \text{ for $P'$ convex}\}$$

One of the fundamental concepts is that of a polytope: there are two equivalent definitions.

A $\mathcal{V}$-polytope is the convex hull of a finite set of points in $\mathbb{R}^n$.

An $\mathcal{H}$-polytope is the intersection of a finite set of closed halfspaces in $\mathbb{R}^n$ (that is; the region enclosed by a set of inequalities).

That these two definitions are equivalent is not trivial, but it has been proven, and it is not what I'm specially interested about.

What I'm interested in is the combinatorial structure of a given polytope (or family of polytopes). We compress all the combinatorial information of a polytope in three fundamental invariants: the $f$, $h$ and $\gamma$-vectors. The $f$-vector is defined as the vector $(f_0, f_1, ... , f_d)$, where $f_i$ denotes the amount of $i$-faces of $P$: $f_0$ is the amount vertices, $f_1$ the amount of edges, etc...

(TODO: $h$ and $\gamma$-vectors. Their relation to the $f$-vector.)

We define the $n$-simplex $\Delta^n$ as the convex hull of $\{e_i : i \in [1, ..., n]\}$, where $e_i$ is the $i$th standard basis vector of $\mathbb{R}^n$. Notice that $\Delta^n$ is affinely independent.

A $d$-polytope $P$ ($d$ dimensions) is simple if each of its vertices is incident to $d$ edges. A $d$-polytope is simplicial if all of its faces are simplices.

(TODO: More definitions, clearer exposition, give intuition. What a bad rhyme.)

Now we turn our attention to a particular way of constructing polytopes: from graphs. Consider a graph $G$ on the labeled vertices $[1, ..., n]$ which is connected (there is a path that connects any pair of vertices, but it needn't be direct). Define the connected building set as the set of all subsets of vertices of $G$, such that the induced subgraph is connected:

$$\mathcal{B}(G) := \{U \subset G : G|_U \text{ is connected}\}$$

The polytope derived from this is defined as the Minkowski sum

$$P_{\mathcal{B}(G)} = \sum_{U\in\mathcal{B}(G)} \Delta_U $$

of $U$-simplices $\Delta_U := ConvexHull(e_i : i \in U)$. We call $P$ a graph-associahedron, and in general, the $P_{\mathcal{B}}$ of some building set $\mathcal{B}$ is called the nestohedron.

It is obvious that the choice of graph will determine the resulting polytope. We will study the polytopes generated by particular kinds of graphs (cyclic, complete, path, stellar, etc...): particularly, we will work towards fully determining their combinatorial structure by finding the $f$, $h$ and $\gamma$ vectors.

Note we required $G$ to be connected, because disconnected elements (their simplex representation are points) have no effect on the Minkowski sum: a point added to anything is just a translation.

My doubts at the moment
So what I'm interested in understanding is how to combinatorially describe a graph-associahedra. The Minkowski sum of simplices gets hairy pretty quickly, and I feel like any insight into the structure of $P_{\mathcal{B}(G)}$ must come from the structure of $G$ itself. But how do I translate graph properties to geometric properties? I'll try to go over simple examples, and generalize from there.

Quick trip to Madrid

Today i visited the Spanish capital for a few hours, with the objective of acquiring a USA student visa for my summer stay in Boston. After completing a few forms (in one of which i had to declare that, in fact, i have not killed anyone, trafficked with anyone, nor extorted, tortured or laundered money), waiting for my turn, and successfully completing a 1-minute Guiness World Record interview, i left just as i had arrived. With a perpetual cold.

Forgot to take pictures of Madrid itself. OUch. But here i post a pair of worthy ones that i took on my way back. There's an insane amount of wind turbines around there. Those would make nice album covers, don't  you think?

I'm working on (ergo, reading + banging my head on) more mathematics, mainly. And thinking about next year's school research project, focusing again on artificial intelligence (with a more minimalist but general approach; think graphs).

On chinese cartoons

After reading exactly 0 pages of manga in the last two years, I somehow got caught up in Oyasumi Punpun. Not the most orthodox choice for a comeback, no the most sensible pick for a tranquil vacational noon.

I didn't know what I expected, and I haven't yet understood why did I even start reading in the first place. But wow, what a ride. I instantly fell in love with everything about it. The narrative, the dialogues... the artistic style is even coherent most of the time (yes, it's a bird, but don't sweat it; if you can't stand a human bird as a protagonist, what will you do when he becomes a pyramid?). I do certainly synchronize quite well with Punpun's initial vibrations, but it becomes harder as the storyline advances, until a point of disconnection (albeit not absolute; there's still a trace of us inside the late Punpun).

Not your pretty, light-hearted chinese cartoon, that is for sure. Sometimes, I asked myself whether it was a bit too pretentious or unnecessarily 'deep', but since everything made a bit of sense in my mind, I leave that for later thought. It's a fact that this work has surprised me far beyond my expectations, and I'm thankful for the... rollercoaster of 12+ hours it has provided me. I will come back to it and read it again someday, but thanks that's enough for today.

If you want to drift away from conventional manga, or are simply in search of something different that will hopefully talk to you more deeply, please consider Oyasumi Punpun. To paint it as a simple love story does not do it justice.

On an other note, it was Bach's birthday (31st of March in New Style date) and I had planned to record a performance of his fugue in E Major from the Well-Tempered Clavier II (BWV 878), but looks like he'll have to wait a bit more for my rendition. Chopin's C Major prelude (Op. 28) and C# minor étude (Op. 25) are on the works as well, but I'm just hopeful on the former.

Two little problems (ii)

Problem 2. Find the solutions of $x^6 + y^6 + z^6 = 6xyz - 3$.

Equalities like this ($xyz$? Sixth powers? I don't know the formula for that!) can look intimidating, but a cool head and some experience will make dealing with such unfamiliar things a bit more familiar.

Tempted to simplify the right hand side, we divide by three:
\[
\frac{x^6 + y^6 + z^6}{3} = 2xyz - 1
\]
The key of the exercise is to notice how the left hand side can be seen as an arithmetic average of 3 values, $x^6$, $y^6$ and $z^6$. Given how either the arithmetic average is always greater than the geometric average, or all the values are equal, we can consider the inequality:
\[
\sqrt[3]{x^6y^6z^6} \leq \frac{x^6 + y^6 + z^6}{3}
\]
And we simplify:
\[
x^2y^2z^2 \leq \frac{x^6 + y^6 + z^6}{3}
\]
We now define $xyz = t$, and proceed to exchange the fraction by the equivalence we first saw:
\[
t^2 \leq 2t - 1
\]
Therefore $(t-1)^2 \leq 0$, which is only possible for $t=1$ (since any other value will result in a positive square).

Now, since the product of the three variables is 1, $\sqrt[3]{x^6y^6z^6} = \sqrt[3]{1^6} = 1$, and going back to the initial equality, $2xyz - 1 = 2 - 1 = 1$, which is equal as well to the arithmetic average, we find that both the $AM$ and the $GM$ are equal, and therefore their elements are equal as well. Then:
\[
x^6 + x^6 + x^6 = 3x^6 = 3
\]
And so $x^6 = 1$. We find six solutions for $x$, all of them being either 1 or -1, but we have to restrict to combinations such that $xyz = 1$, which is left as a petty exercise for the reader.

We did this problem in class, and everyone was quite fascinated with how the problem simply unraveled with the use of such elementary methods. Admittedly, it's a very synthetic problem, but it testes your ability to see that which is not immediately obvious to the eye.

Problem 3. Any power $n^k$ can be expressed as the sum of $n$ consecutive odd integers.

This one comes from proving the $2^k$ case, and then being asked to do the same with $3^k$. It seemed too good to be true, but as it turns out, the proof is quite simple.

We assert the theorem:
\[
n^k = (2q + 1) + (2q + 3) + (2q + 5) + ... + (2q + (2n - 1))
\]
Let's reorder this:
\[
n^k = n2q + (1 + 3 + 5 + 7 + ... (2n - 1))
\]
It is a fact that the sum of the first $r$ odds is equal to $r^2$ (it's a one-line proof), so:
\[
n^k = n2q + n^2
\]
We find $q$:
\[
q = \frac{n^{k-1} - n}{2}
\]
And then verify the identity:
\[
n^k = n2\left(\frac{n^{k-1} - n}{2}\right) + n^2 = n(n^{k-1} - n) = n^n - n^2 + n^2 = n^k
\]
And we're done; the identity derived from the sum of $n$ consecutive odd integers is proved to be equal to $n^k$!

Snow

Today has been a snowy day (not in the most rigorous sense of the word) all around the country. The camera struggled with such little amount of light, but it pulled this one off somehow, which looks cool enough.

Visit to the MNAC (National Art Museum of Catalonia)

This weekend i visited the National Art Museum of Catalonia for a few hours. Sadly, i couldn't take the camera with me, so all pictures were taken with my phone.

[algebra] A little problem (ii)

I'm following the great course on abstract algebra offered online by Harvard, lectured by Benedict Gross. So far, i'm having a great time. I'm trying to do the exercises (Algebra, Artin, 1st ed. 1991), to gain a better understanding and intuition on the matter, so i'll be posting exercises that i find interesting. Mind you, i'm just getting started, so interesting may be a bit too far-fetched...

Exercise (2.2.20.a): Let $G$ be an abelian group, and $a,b \in G$. Let $m,n$ be the orders of the groups generated by $\langle a \rangle$ and $\langle b \rangle$. What can you say about the order of $\langle ab \rangle$?

We consider the elements generated by $\langle ab \rangle$:

• 1 (identity).
• $ab$.
• $(ab)^2 = abab$. Since the group is commutative, we can reorder like this: $aabb = a^2b^2$.
• $(ab)^k = a^kb^k$, more generally.

Therefore, once we reach either $(ab)^m$ or $(ab)^n$, whichever's the smallest of $m$ and $n$, we will be left with the rest of the cyclic group generated by $a$ or $b$. So, we can conclude that the order of $\langle ab \rangle$ is in fact the order of $a$ or $b$.

A little problem (i)

Problem 1. Demostra que ${1992 \choose 1492}$ no és divisible per 500 -- Prove that ${1992 \choose 1492}$ is not divisible by 500.

Given that we're asked to prove divisibility, decomposing the numbers in prime factors is a nice idea in order to get somewhere. $1992 = 2^3 \cdot 3 \cdot 83$, $500 = 2^2 \cdot 5^3$ and $1492= 2^2 \cdot 373$. Let's now analyze the binomial expansion:
\[\frac{1992!}{(1992-1492)! \cdot 1492!} = \frac{1992!}{500! \cdot 1492!}\]
We're asked to prove that the quotient will not be divisible by 500, and so after we simplify the expression, we must find that there are less than two 2s and three 5s left. Proving one of these two conditions will solve the problem. However the denominator simplifies with the numerator, we should find that there are not enough factors left to form the number 500.

In this case, intuition told me that there were going to be enough 2s left, and so i jumped straight into finding out how many 5s were going to be left. Either way, the process is similar.

We must count the amount of 5s we will have in the numerator, in that gigantic factorial. To do so, we have to check how many multiples of $5$, $5^2$, $5^3$ ... there are (until we get to the point where $5^x$ is more than 1992). We can take the fifth root to find $x$, like so:
\[ \lfloor \sqrt[5]{1992} \rfloor = 4 \]
So, we have to count the multiples of up to $5^4$:
\[ \sum_{n=1}^{4} \lfloor \frac{1992}{5^n} \rfloor = 398 + 79 + 15 + 3 = 495  \]
Therefore, we have a total of $495$ 5s somewhere in the numerator. Fairly enough, we simply have to check how many 5s we have in the denominator and see if the difference is less than 3. For 500, we take the fifth root and find that we can find multiples of up to $5^3$. We take the fifth root again for 1492 and 4 is the exponent.
\[ \sum_{n=1}^{3} \lfloor \frac{500}{5^n} \rfloor = 100 + 20 + 4 = 124 \]
\[ \sum_{n=1}^{4} \lfloor \frac{1492}{5^n} \rfloor = 298 + 59 + 11 + 2 = 370 \]

And nicely enough, the total amount of 5s we have in the denominator is 494, which leaves us with a single, poor 5 once the fraction is simplified. Not enough to form a 500, and so the problem is solved.

Easy (relatively, but uncommon, surely) problems like these help keep the brain alive in the cold winter school days. Take a stand and keep yours active! This is a problem from the Catalonian regional phase of the math Olympiads, back in 1992.

Some pictures

Not much time left until the restart of routine, so i'm already psychologically torturing myself over it, i can't help it.