0xDE () wrote,

# 1317131 and majorization by subsequences

My latest preprint to appear on the arXiv is "Superpatterns and Universal Point Sets" (with Michael Bannister, Jack Cheng, and Will Devanny, to appear at GD 2013, arXiv:1308.0403). The main idea of the paper is to connect two open problems from different areas of research, the size of universal point sets in graph drawing and the size of superpatterns in the theory of permutation patterns, and maybe make progress on both sides.

You can read about the details in the paper, but I wanted to highlight something else, a tool we use in both this and the previous preprint that isn't really about graph drawings or permutations. It's the integer sequence

1,3,1,7,1,3,1,15,1,3,1,7,1,3,1,... (OEIS A038712)
where each term is one less than a power of two. The nth term in the sequence can be generated as the exclusive-or of the two consecutive integers n − 1 and n; for instance, the sixth term, 3, is the exclusive or of 5 and 6 (101 and 110 in binary).

This sequence has a neat and useful property: if any other sequence xi of finitely many integers adds to a number n, then we can find a subsequence yi of the first n numbers in the 1,3,1,7 sequence that majorizes the given sequence, meaning that each yi is greater than or equal to xi. For instance, the sequence 1,4,2,1 adds to 8, and among the first eight terms of the 1,3,1,7 sequence we find a subsequence 1,7,3,1 that is at least as large at each element.

This subsequence domination property wouldn't be so interesting by itself (the sequence 1,2,3,4,... has the same property) but the 1,3,1,7 sequence also has particularly small partial sums. The sum of the first n terms of the sequence can be calculated quickly (much more quickly than just computing the sum directly, for large n) by a simple trick: represent n as a sum of distinct powers of two (its binary representation), and sum up the numbers 2i(i + 1) for each of the powers 2i appearing in this sum. For instance, 6 = 22 + 22 and the sixth partial sum, 16, equals 22(2 + 1) + 22(1 + 1). Using this formula, we can show that the nth partial sum is always between n log2 n − 2n and n log2 n + n, solving a conjecture in OEIS A080277. And every sequence with the subsequence domination property has partial sums at least proportional to n log n, so up to constant factors the sequence 1,3,1,7,... is optimal.

• Post a new comment

#### Error

default userpic