4 ms·
A very nice fact that I coincidentally learned just yesterday, which is not in the linked answer but is touched on in one of the comments and in an edit on the
by svat 4y ago
A very nice fact that I coincidentally learned just yesterday, which is not in the linked answer but is touched on in one of the comments and in an edit on the accepted answer: there is an explicit bijection that maps a binary tree to seven binary trees (and vice-versa, by the inverse function).
Consider the definition of a binary tree: "a binary tree is either empty, or is a root with a left tree and a right tree". This we can write as
T = 1 + T²
Solving the analogous equation z = 1 + z² in the complex numbers gives z to be a primitive sixth-root of unity (https://www.wolframalpha.com/input?i2d=true&i=z+%3D+1+%2B+Power%5Bz%2C2%5D https://www.wolframalpha.com/input?i2d=true&i=z+%3D+1+%2B+Po...), i.e. z⁶ = 1, and so z⁷ = z. It turns out that we can similarly show T⁷ = T with some algebra (without subtractions) by repeatedly applying the transformations T→1+T² or 1+T²→T (a "game" version is at http://lebarde.alwaysdata.net/seventrees/ http://lebarde.alwaysdata.net/seventrees/):
T⁷
= T⁶ + T⁸
= T⁵ + T⁷ + T⁸
= T⁴ + T⁶ + T⁷ + T⁸
= T⁴ + 2T⁷
= T³ + T⁵ + 2T⁷
= T³ + T⁶ + T⁷
= T² + T⁴ + T⁶ + T⁷
= T² + T⁵ + T⁷
= T² + T⁶
= T + T³ + T⁶
= T + T² + T⁴ + T⁶
= T + T² + T⁵
= 2T + T³ + T⁵
= 2T + T⁴
= 1 + T + T² + T⁴
= 1 + T + T³
= 1 + T²
= T
This can be used to give an explicit bijection: see Andreas Blass's paper "Seven trees in one": https://arxiv.org/pdf/math/9405205 https://arxiv.org/pdf/math/9405205 (via https://twitter.com/CihanPostsThms/status/1579017713527050241 https://twitter.com/CihanPostsThms/status/157901771352705024... — see also https://math.ucr.edu/home/baez/week202.html https://math.ucr.edu/home/baez/week202.html which has more.)
- mjcohen 4y agoWouldn't t be a cube root of -1? t=t^2+1 => 0=t^2-t+1 => 0=(t+1)(t^2-t+1)=t^3+1
- 6gvONxR4sf7o 4y agoSame thing. A cube root of -1 is a sixth root of 1.
- travisgriggs 4y ago"Bijection" -> https://en.wikipedia.org/wiki/Bijection https://en.wikipedia.org/wiki/Bijection Monday was looking boring. I'm excited now about the new adventure I've set for myself to somehow inject this (new for me) term into a discussion appropriately.
- harveywi 4y agoAs long as you surject it whenever you inject it you'll be fine.
- krastanov 4y agoThis is fascinating, but I am still curious: would I ever have a good reason to repackage seven binary trees as one (or other way around)?
- hither_shores 4y agoThe particular example is not the point. The question you should be asking is > would I ever have a need to understand what happens when you perform algebraic manipulations on data structures and the answer is as usual that it depends on what you're working on. Parsers? Absolutely. CRUD apps? Yes, but only if you look for them. Numerical linear algebra? Probably not.
- feoren 4y ago> CRUD apps? Yes, but only if you look for them. I upvoted just for this breath of fresh air right here. CRUD apps are boring and crappy because people make them boring and crappy. I find uses for this type of thing all the time in "boring" CRUD apps, because I look for them.
- svat 4y agoI can't imagine any application. :-) The fascination is more that of explanation: if you treat T = 1 + T^2 as an algebraic equation in the complex numbers, you can get a lot of expressions that are meaningless: it's hard to make sense of T = 1/2 ± i√3/2 or T^3 = -1 or even T^6 = 1 (there is certainly no bijection sending six trees to the empty tree). But then, T^7 = T is suddenly very much meaningful and we can turn it into an explicit description. What's going on? Which equations are "meaningful" and which are not? Blass's paper gives an explanation: an equation is meaningful if you can derive it by working in (something like) N[T]/(T = 1 + T^2) (with some more conditions). Baez's discussion (linked above) puts it in terms of "categorification", and is also interesting.
- jerf 4y agoThis is like giving an artist a new shade of color they've never had before, like a new rich blue or something. It isn't that everything is improved by using that new color as much as possible everywhere. It's that it opens up new possibilities you may never have considered before. This insight may be useless, but there are other useful ones that can emerge that you wouldn't have thought of on your own in a long time.