A265262 The tree of hemitropic sequences read by rows, arising from an Erdős-Turán conjecture.

1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2

Offset: 0

Author

Labib Haddad and Michel Marcus, Dec 06 2015

Keywords

• nonn
• tabf

Comments

Let A be a subset of the set N of nonnegative integers. Let pA(n) be the number of pairs (x, y) of elements of A such that n = x + y and x <= y. The sequence pA = [pA(0), pA(1), ... , pA(n), ... ] is called the profile of A. A Sidon set is a subset A whose profile has only 0's and 1's.

An [order 2 additive] basis of N is a subset A whose profile has no 0’s. Erdős and Turán conjectured that the profile of a basis is always unbounded (see the Erdős and Turán link). The conjecture is, up till now, still undecided.

The tree below displays the infinite sequences [1, pA(2), . . . ], associated to the profiles pA = [1, 1, pA(2), . . . ] of all the subsets A of N to which 0 and 1 belong. Those are the so-called hemitropic sequences. The Erdős-Turán conjecture would not hold if (and only if) the tree contained an infinite bounded branch with no 0's.

The length of the n-th row is 2^n. The right leaf of a node is equal to the left leaf + 1.

Examples

			First few levels of the tree:
                       1;
           1,                      2;
     0,          1,          1,         2;
  0,    1,    1,    2,    1,    2,    2,   3;
0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;
...
First few rows of the irregular array:
1;
1, 2;
0, 1, 1, 2;
0, 1, 1, 2, 1, 2, 2, 3;
0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3;
...
		

Links

• Michel Marcus, Table of n, a(n) for n = 0..8190
• P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.
• Labib Haddad, Some peculiarities of order 2 bases of N and the Erdos-Turan conjecture, arXiv:1507.05849 [math.NT], 2015 (see The binary tree of hemitropic sequences chapter).
• Wikipedia, Erdős-Turán conjecture on additive bases

Crossrefs

Cf. A004137, A066062, A217793.

Programs

Maple

with(ListTools):
v:=n->Reverse( convert(n,base,2)):
m:=n->nops(v(n)):
c:=n-> v(n)[m(n)] + sum(v(n)[k]*v(n)[m(n)-k],k=1..floor(m(n)/2)):
d:= h->[seq(c(n),n=2^h..2^(h+1)-1)]: # the h-th row
f:= p->[seq(c(n),n=1..p)]: # the first p terms

PARI

f(t,n,va) = 1+ sum(k=1, n+1, va[k]*t^k);
row(n) = {if (n==0, vc = [1], vc = []; for (ni = 2^n, 2^(n+1)-1, b = binary(ni); ft = f(t, n, b); pt = (f(t, n, b)^2 + f(t^2, n, b))/2; vc = concat(vc, polcoeff(pt, n+1)););); vc;}
tabf(nn) = for (n=0, nn, vrow = row(n); for (k=1, #vrow, print1(vrow[k], ", ")); print());

Formula

For each k>=0, let u(k)=1 if k is in A, u(k)=0 is k is not in A. Then pA(n) = Sum_{k=0..floor(n/2)} u(k)*u(n-k). See formula (5) on p. 8 and p. 28 in Haddad link.