The hexachordal theorem
by math_explorer, Jan 25, 2020, 3:55 AM
Let
be a positive integer. Let
be a subset of
with size
. We denote the complement of
with respect to
as
.
Let
be an element of
.
Let
be the number of ordered pairs
such that
.
Theorem. For all
,
.
Proof. Let
. Let
. They are the same size:
. So their differences
and
are the same size too. But
is precisely
and
is precisely
(why?). ![$\square$](//latex.artofproblemsolving.com/b/6/c/b6cf65b1f2fbdf388e3daeff9b96b34d3399d777.png)
Remark. This is more or less what's known as the "Hexachordal theorem" in "musical set theory". The usual interpretation is when
,
is identified with the pitch classes in twelve-tone equal temperament, and
is a "hexachord", a set of six pitch classes. Apparently there is also a crystallography interpretation.
This is a paper on a generalization and I love how many citations they managed to come up with for proofs, some of which are apparently more concise than others: http://cs.smith.edu/~jorourke/Papers/CHexa-MCM.pdf
![$n$](http://latex.artofproblemsolving.com/1/7/4/174fadd07fd54c9afe288e96558c92e0c1da733a.png)
![$R$](http://latex.artofproblemsolving.com/e/f/f/eff43e84f8a3bcf7b6965f0a3248bc4d3a9d0cd4.png)
![$\mathbb{Z}/2n\mathbb{Z}$](http://latex.artofproblemsolving.com/f/c/e/fcea38d92a8d814b1a17558353a369636c329c5f.png)
![$n$](http://latex.artofproblemsolving.com/1/7/4/174fadd07fd54c9afe288e96558c92e0c1da733a.png)
![$R$](http://latex.artofproblemsolving.com/e/f/f/eff43e84f8a3bcf7b6965f0a3248bc4d3a9d0cd4.png)
![$\mathbb{Z}/2n\mathbb{Z}$](http://latex.artofproblemsolving.com/f/c/e/fcea38d92a8d814b1a17558353a369636c329c5f.png)
![$\overline{R}$](http://latex.artofproblemsolving.com/7/5/3/753dc004105a6b3c558defb100e77a617e26971c.png)
Let
![$d$](http://latex.artofproblemsolving.com/9/6/a/96ab646de7704969b91c76a214126b45f2b07b25.png)
![$\mathbb{Z}/2n\mathbb{Z}$](http://latex.artofproblemsolving.com/f/c/e/fcea38d92a8d814b1a17558353a369636c329c5f.png)
Let
![$H(R, d)$](http://latex.artofproblemsolving.com/5/b/0/5b0e73aa1ceb4ad881a31958b60f959b93283df5.png)
![$(a, b) \in R^2$](http://latex.artofproblemsolving.com/e/9/e/e9eb0c29a8c703400d5f424230ab710902cbaf23.png)
![$b - a \equiv d \bmod{2n}$](http://latex.artofproblemsolving.com/5/d/9/5d96d218d7abc775226f0149f52fdbc76fcbd069.png)
Theorem. For all
![$d$](http://latex.artofproblemsolving.com/9/6/a/96ab646de7704969b91c76a214126b45f2b07b25.png)
![$H(R, d) = H(\overline{R}, d)$](http://latex.artofproblemsolving.com/9/3/9/939e1d361af19182f0fa9b9da03b482ce0cdebda.png)
Proof. Let
![$A = \{ (a, a + d) \mid a \in R \}$](http://latex.artofproblemsolving.com/8/8/0/880aa2534536abeb6ed920396dfdabcfc72bad50.png)
![$B = \{ (b - d, b) \mid b \in \overline{R} \}$](http://latex.artofproblemsolving.com/c/7/8/c78fcf1bdf5e20cae902f3e86105863cbbdcc044.png)
![$|A| = |R| = n = |\overline{R}| = |B|$](http://latex.artofproblemsolving.com/0/b/7/0b7b73e3b5696ff932dd1dac2f197e7d3d50e41f.png)
![$A \setminus B$](http://latex.artofproblemsolving.com/c/2/7/c2758378a3fb14723f8ed57dc88fdce4573791ef.png)
![$B \setminus A$](http://latex.artofproblemsolving.com/3/1/6/316e7f7b0d980fa7d45537c3116574b95bebe0c7.png)
![$|A \setminus B|$](http://latex.artofproblemsolving.com/4/9/3/493e2fb3195d435555f1513ca488e6b7624425e6.png)
![$H(R, d)$](http://latex.artofproblemsolving.com/5/b/0/5b0e73aa1ceb4ad881a31958b60f959b93283df5.png)
![$|B \setminus A|$](http://latex.artofproblemsolving.com/3/f/f/3ff120655226cf7b750916894115ed702c5222ea.png)
![$H(\overline{R}, d)$](http://latex.artofproblemsolving.com/d/1/d/d1d201f5a36fc165dbfe6e648d88673f8611b41a.png)
![$\square$](http://latex.artofproblemsolving.com/b/6/c/b6cf65b1f2fbdf388e3daeff9b96b34d3399d777.png)
Remark. This is more or less what's known as the "Hexachordal theorem" in "musical set theory". The usual interpretation is when
![$n = 6$](http://latex.artofproblemsolving.com/e/3/2/e326b48726d4c73525c3b980409600fd87ea9846.png)
![$\mathbb{Z}/2n\mathbb{Z}$](http://latex.artofproblemsolving.com/f/c/e/fcea38d92a8d814b1a17558353a369636c329c5f.png)
![$R$](http://latex.artofproblemsolving.com/e/f/f/eff43e84f8a3bcf7b6965f0a3248bc4d3a9d0cd4.png)
This is a paper on a generalization and I love how many citations they managed to come up with for proofs, some of which are apparently more concise than others: http://cs.smith.edu/~jorourke/Papers/CHexa-MCM.pdf
some unfinished business
by math_explorer, Sep 10, 2019, 1:02 PM
Three months ago I learned that I've been learning about regular expressions (in the mathematical concept sense, not the text processing tool sense) wrong. Regex derivatives are much better.
———
I posted Olympiads: The Infinitely Overdue Retrospective on my Other Blog half a year ago. It's probably the most topical thing I've done this year.
———
The quote that used to be in the blog description has probably run its course. It used to be possible to source it with clever Googling, but I can't any more. It is from a comment on this post: https://artofproblemsolving.com/community/c1936h1400505
I have gathered more evidence in support of this hypothesis.
———
I posted Olympiads: The Infinitely Overdue Retrospective on my Other Blog half a year ago. It's probably the most topical thing I've done this year.
———
The quote that used to be in the blog description has probably run its course. It used to be possible to source it with clever Googling, but I can't any more. It is from a comment on this post: https://artofproblemsolving.com/community/c1936h1400505
r31415 wrote:
Is everyone on AoPS the same person??
I have gathered more evidence in support of this hypothesis.
Ultimate combo breaker
by math_explorer, Feb 28, 2018, 3:51 AM
Since I started this blog I made at least one post every month for 89 months in a row, until last month. Welp. At least 89 is a Fibonacci number.
Most of the people I met on AoPS, I now know better through offsite contact channels. I suspect I'm less of a mathematician than I was when I started out here, and I'm definitely less of a math competitor than I was when I started out here. I'm OK with all of this. That's how the nature of things turned out to be.
If you're reading this and feel comfortable doing so, please leave a comment.
Probabilistically, farewell.
Most of the people I met on AoPS, I now know better through offsite contact channels. I suspect I'm less of a mathematician than I was when I started out here, and I'm definitely less of a math competitor than I was when I started out here. I'm OK with all of this. That's how the nature of things turned out to be.
If you're reading this and feel comfortable doing so, please leave a comment.
Probabilistically, farewell.
Differential
by math_explorer, Dec 16, 2017, 6:03 PM
Number theory is really hard
by math_explorer, Nov 27, 2017, 1:13 AM
I have never typeset so many Fraktur letters in my life before.
If you read my other blogs you should know stuff is being shaken up right now.
Post in November. I'm old (???)
If you read my other blogs you should know stuff is being shaken up right now.
Post in November. I'm old (???)
Eighteenth-century nonsense
by math_explorer, Oct 29, 2017, 11:31 PM
Passing memes between social platforms (and posting in October)...
Let
be the set of rooted binary trees, where we include the empty tree with 0 nodes. There is an obvious bijection between nonempty trees in
and pairs of trees in
, by taking the left and right subtree of
. So there is an obvious bijection between
and {the empty tree, plus pairs of trees in
}.
Let's write this as
, so
. In other words,
is a sixth root of unity.
So
. Unfortunately this is absurd because there is more than one 6-tuple of trees.
But, let's try again and write
. And in fact:
Now the question is, of course: how did treating
, an infinite set of combinatorial objects, as a complex number produce a reasonable theorem?
It turns out there's some ring theory you can pull to see why this is the case. Some arXiv papers on the subject: https://arxiv.org/pdf/math/9405205v1.pdf https://arxiv.org/abs/math/0212377
Let
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
Let's write this as
![$T = T^2 + 1$](http://latex.artofproblemsolving.com/a/1/6/a169f9b4583ca40de86812bd57d91adf03a51b8c.png)
![$T^2 - T + 1 = 0$](http://latex.artofproblemsolving.com/5/e/2/5e248b3d34025a56fb043b8959920c463ca59c29.png)
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
So
![$T^6 = 1$](http://latex.artofproblemsolving.com/5/7/e/57e7ef8d199e11d24782402b352161eab8381d45.png)
But, let's try again and write
![$T^7 = T$](http://latex.artofproblemsolving.com/c/c/7/cc72bb64eac403582e324c5a9421b9ad1606e54d.png)
- There is a "very explicit" bijection between the set of 7-tuples of trees, and the set of all trees. Here "very explicit" means that to map 7 trees to 1, you just need to inspect the 7 trees down to a fixed finite depth, independent of what the trees actually are, to construct some part of the 1 tree. Then you can paste the subtrees beneath that depth to subtrees of what you constructed.
- This is tight: there exists a very explicit bijection between the set of
-tuples of trees and trees iff
.
Now the question is, of course: how did treating
![$T$](http://latex.artofproblemsolving.com/2/5/5/2554b6496c3b678897e9b060ef00aa9f0a7d7ece.png)
It turns out there's some ring theory you can pull to see why this is the case. Some arXiv papers on the subject: https://arxiv.org/pdf/math/9405205v1.pdf https://arxiv.org/abs/math/0212377
Some really bad rings
by math_explorer, Sep 26, 2017, 12:36 AM
Consider
where you adjoin infinitely many free variables. This has infinite Krull dimension because ideals
are all prime. It's also local; the ideal generated by all the variables is the unique maximal ideal.
Consider
; think of
like an infinity. It is local because
is the unique maximal ideal. The ideal generated by all
is prime; that maximal ideal
divides it infinitely many times.
Consider
, the ring of polynomials with integer constant coefficient. Each integer prime or prime integer or something
generates a maximal ideal
. The intersection of those infinitely many maximal ideals is the prime ideal
.
![$\mathbb{Q}[x_1, x_2, x_3, \ldots]$](http://latex.artofproblemsolving.com/a/4/e/a4e4266f8010c8ef30cab8ea7aba4bd45d11b5d8.png)
![$(x_1, x_2, \ldots, x_n)$](http://latex.artofproblemsolving.com/6/9/8/6980e5c3ab8968b6e4fbd15f97e65029568ea893.png)
Consider
![$\mathbb{Q}[x, x^{\omega-n}\text{ for all }n \in \mathbb{Z}]$](http://latex.artofproblemsolving.com/e/4/9/e49d2dc455fa0b66df6efb95c72a6007cce6e850.png)
![$\omega$](http://latex.artofproblemsolving.com/5/4/d/54d7d48553f4d9e7ab418118607ea324cbfddfda.png)
![$(x)$](http://latex.artofproblemsolving.com/b/5/5/b558769a96459d2be8d1b67f24da056bb02f6399.png)
![$x^{\omega-n}$](http://latex.artofproblemsolving.com/1/b/2/1b22fce1ff18526d8ef642aeff2531f4dd6a6dd4.png)
![$(x)$](http://latex.artofproblemsolving.com/b/5/5/b558769a96459d2be8d1b67f24da056bb02f6399.png)
Consider
![$\mathbb{Z} + x\mathbb{Q}[x]$](http://latex.artofproblemsolving.com/9/8/e/98ebc9f23f78305d98bd7816632348f36b065aba.png)
![$p$](http://latex.artofproblemsolving.com/3/6/f/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png)
![$(p)$](http://latex.artofproblemsolving.com/0/6/9/06951608bb7d5149ead75be808bdbf1559422b84.png)
![$(x)$](http://latex.artofproblemsolving.com/b/5/5/b558769a96459d2be8d1b67f24da056bb02f6399.png)
How to solve a differential equation
by math_explorer, Aug 23, 2017, 7:36 PM
0. Try solutions of the form
. If everything involving
cancels out, multiply your solution by
and try again. Repeat as desired.
0a. Sines and cosines are just linear combinations of complex exponentials, but handy if you need to show your solution to somebody who is Afraid Of Complex Numbers
. (Jeez U+2122 is a really normal Unicode character, AoPS.)
1. If there's a
term and a
term, each multiplied by functions of
, manipulate it to get something that's a derivative of something of the form
. It is generally helpful to realize that
and that
is the ratio between the
term and the
term.
2. If that doesn't work you can always do it numerically.
![$y = Ae^{Bx}$](http://latex.artofproblemsolving.com/8/d/6/8d6a24d1452b357d3c7f226c1f31d11360e94bf1.png)
![$y$](http://latex.artofproblemsolving.com/0/9/2/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png)
![$x$](http://latex.artofproblemsolving.com/2/6/e/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png)
0a. Sines and cosines are just linear combinations of complex exponentials, but handy if you need to show your solution to somebody who is Afraid Of Complex Numbers
![$^{\textsf{TM}}$](http://latex.artofproblemsolving.com/8/b/1/8b14015bb7bf15de4a9a7ec6e98ed2efa23dfc03.png)
1. If there's a
![$y'$](http://latex.artofproblemsolving.com/1/9/a/19ac5343ae3e72d247f8e2d0ec7757ae5cca2634.png)
![$y$](http://latex.artofproblemsolving.com/0/9/2/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png)
![$x$](http://latex.artofproblemsolving.com/2/6/e/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png)
![$f(x)y$](http://latex.artofproblemsolving.com/8/f/e/8fe1f915c9a2ae824c6e3540de5089a88549d4c7.png)
![\[ \frac{d}{dx} e^{r(x)}y = e^{r(x)}(r'(x)y + y') \]](http://latex.artofproblemsolving.com/1/8/0/180d39e1050f5e585c7d2db5128f21c019b75a5c.png)
![$r'(x)$](http://latex.artofproblemsolving.com/5/d/1/5d1ca686a341c0be0c40264ee6b12499952a2f81.png)
![$y$](http://latex.artofproblemsolving.com/0/9/2/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png)
![$y'$](http://latex.artofproblemsolving.com/1/9/a/19ac5343ae3e72d247f8e2d0ec7757ae5cca2634.png)
2. If that doesn't work you can always do it numerically.
♪ i just hope you understand / sometimes the clothes do not make the man ♫ // https://beta.vero.site/
Archives
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
![+](/m/community/img/blogs/hyperion/plus.gif)
Shouts
Submit
91 shouts
Contributors
Tags
About Owner
- Posts: 583
- Joined: Dec 16, 2006
Blog Stats
- Blog created: May 17, 2010
- Total entries: 327
- Total visits: 352836
- Total comments: 368
Search Blog