Balance constants are not well-ordered!
Oct. 2nd, 2021 04:30 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo, background. Given a finite partial order P, consider all linearizations of P; then for any pair {a,b} of distinct elements of P, we can look at which fraction of linearizations order the two elements one way (a<b) vs the other way (b<a). Well, we have two fractions here, the fraction that do a<b and the fraction that do b<a; in order to associate a specific number, we'll go with whichever is smaller. We can then define the "balance constant" of P, denoted b(P) or δ(P) [I'll go with b(P)], to be the largest of these fractions over all pairs {a, b} of distinct elements of P.
The famous 1/3-2/3 conjecture states that, if b(P) is not zero (i.e., if P is not a total order), then b(P)≥1/3.
Now, as I've written about before, my opinion is that when you see a gap (even just a conjectured one :) ), you should ask if that gap is the start of a well-ordering! And one of my examples was the 1/3-2/3 conjecture. So: Are balance constants well-ordered?
Well, I just learned from Felix Bauckholt that they are not! Their argument, skipping a lot of the details to establish this stuff, went as follows:
Define the ladder poset Ln to be the ordering on {1, 2, ..., n} defined by taking the transitive closure of k<k+2 and k<k+3. So the only pairs not ordered are pairs of the form {k, k+1}. Then:
1. The number of linearizations of Ln is Fn+1, where Fk denotes the Fibonacci numbers.
2. Of these linearizations, FkFn-k have k<k+1, while Fk+1Fn-k+1 have k+1<k; so the fraction for this pair is FkFn-k/Fn+1;
3. Applying Vadja's identity, we can see that this is maximized when k=1, so the balance constant of Ln is Fn-1/Fn+1;
4. And if we restrict to the case of n odd, then we can apply it again in the form of Catalan's identity and see that this subsequence is strictly decreasing (which as we know has limit 1/φ², where φ is the golden ratio). (To be more general, the whole series converges to 1/φ² in an alternating manner.)
So that does it! Balance constants are not well-ordered! Kind of disappointing that they're not, but I still think that's a really cool resolution! Thanks so much to Felix for showing me this!
Admittedly this doesn't leave me with many examples for "when you see a gap you should look for a well-order". :P Those various classes of real algebraics were already ruled out when I wrote my previous entry on the subject, and here goes this one. That just leaves me with generalizations of integer complexity defects, and word satisfaction probabilities in groups. Both of which contain endless examples, admittedly, but I would like more distinct ones. Well, if you know any I should add to my list, do let me know. :)
-Harry
Addendum October 10: Actually, now I'm really wondering whether 1/φ² might be the smallest limit of balance constants. Well, if it is, presumably it won't be proven for a long time...
The famous 1/3-2/3 conjecture states that, if b(P) is not zero (i.e., if P is not a total order), then b(P)≥1/3.
Now, as I've written about before, my opinion is that when you see a gap (even just a conjectured one :) ), you should ask if that gap is the start of a well-ordering! And one of my examples was the 1/3-2/3 conjecture. So: Are balance constants well-ordered?
Well, I just learned from Felix Bauckholt that they are not! Their argument, skipping a lot of the details to establish this stuff, went as follows:
Define the ladder poset Ln to be the ordering on {1, 2, ..., n} defined by taking the transitive closure of k<k+2 and k<k+3. So the only pairs not ordered are pairs of the form {k, k+1}. Then:
1. The number of linearizations of Ln is Fn+1, where Fk denotes the Fibonacci numbers.
2. Of these linearizations, FkFn-k have k<k+1, while Fk+1Fn-k+1 have k+1<k; so the fraction for this pair is FkFn-k/Fn+1;
3. Applying Vadja's identity, we can see that this is maximized when k=1, so the balance constant of Ln is Fn-1/Fn+1;
4. And if we restrict to the case of n odd, then we can apply it again in the form of Catalan's identity and see that this subsequence is strictly decreasing (which as we know has limit 1/φ², where φ is the golden ratio). (To be more general, the whole series converges to 1/φ² in an alternating manner.)
So that does it! Balance constants are not well-ordered! Kind of disappointing that they're not, but I still think that's a really cool resolution! Thanks so much to Felix for showing me this!
Admittedly this doesn't leave me with many examples for "when you see a gap you should look for a well-order". :P Those various classes of real algebraics were already ruled out when I wrote my previous entry on the subject, and here goes this one. That just leaves me with generalizations of integer complexity defects, and word satisfaction probabilities in groups. Both of which contain endless examples, admittedly, but I would like more distinct ones. Well, if you know any I should add to my list, do let me know. :)
-Harry
Addendum October 10: Actually, now I'm really wondering whether 1/φ² might be the smallest limit of balance constants. Well, if it is, presumably it won't be proven for a long time...
