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 \( n \)th 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 \( x_i \) of finitely many integers adds to a number \( n \), then we can find a subsequence \( y_i \) of the first \( n \) numbers in the 1,3,1,7 sequence that majorizes the given sequence, meaning that each \( y_i \) is greater than or equal to \( x_i \). 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 \( 2^i(i+1) \) for each of the powers \( 2^i \) 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 \( n \)th partial sum is always between \( n\log_2 n - 2n \) and \( n\log_2 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.




Comments:

irishoak:
2013-08-09T06:53:26Z

"up to a constant factor" --- in fact, this factor is \( 1 \). Moreover, if we consider the domination property for a fixed \( n=2^k-1 \), then the sum of our \( n \) terms in 1317 sequence is the minimum possible.

By considering sequences of the form \( 1, 1, \dots, 1, d,1,1,\dots,1 \) we get that each dominating sequence satisfies the condition: For any \( d \) consecutive terms, one is not smaller than \( d \). (In fact, this property is equivalent to dominating, as an easy induction shows.)

Applying this for the numbers of the form \( 2^i-1 \), we get that the sequence contains:

  • at least one number not less than \( 2^k-1 \);
  • at least three numbers not less than \( 2^{k-1}-1 \) (including mentioned above);
  • \( \dots \)
  • at least \( 2^{k-1} \) numbers not less than \( 2^2-1 \) (including mentioned above);
  • at least \( 2^k-1 \) numbers not less than \( 1 \) (including mentioned above).

(In the 1317 sequence all these `at least' come to equalities.) The standard Abel summation now shows the desired minimality of the sum.

If \( 2^{k-1}-1 \lt n \lt 2^k-1 \), then the optimal sequence is obtained from the intial piece of 1317 by replacing \( 2^k-1 \) by \( n \).

11011110: 2013-08-10T02:04:26Z Neat — thanks for the comment! Do you happen to know whether any of this is already published anywhere? It seems like the sort of thing that could have come up in other contexts.