Number triangle

Question

This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary representation (without any extra zeros padded). The next row of triangle is obtained by XOR-ing (adding modul0 2) two consecutive digits of above row, and so on till completion. $$ 1~~1~~0~~1~~0~~1\\ 0~~1~~1~~1~~1\\ 1~~0~~0~~0\\ 1~~0~~0\\ 1~~0\\ 1 $$ Now read off the numbers at the boundary of the triangle, clockwise. In the above example, that would be $1~1~0~1~0~1$, $1~1~0~0~0~1$ and $1~1~1~1~0~1$. That would be the triplet $(53, 49, 61)$. Note that if one had started with binary representation of 49 or 61 as the first row, the resulting triplet will be the same set of three numbers. In some sense, this is well-defined triplet.

Now, consider the number 13. We get the triangle: $$ 1~~1~~0~~1\\ 0~~1~~1\\ 1~~0\\ 1 $$ Reading off numbers clockwise gives $(13,13,13)$, which is somewhat interesting. The same happens for numbers like 11, 39, 57 and so on. I wrote a code on python to get this sequence of special numbers till 500000. The graph below (which looks piecewise linear) depicts the number of integers less than a given integer which have this special property.

Here are a few more observations/questions:

1. Pasted the first ten numbers of this sequence (11, 13, 39, 57, 83, 91, 101, 109, 151, 233, 543, 599) into OEIS, and it did not result in anything. Is there any literature on this?

2. The sequence can be seen as a set of solutions to a linear system of equations in $F_2$, as XOR operation is equivalent to addition in $F_2$. Could that be used to prove that this sequence is (in)finite?

3. The same can be done for a representation in any base. How would that compare to the binary one?

4. How does one explain the graph?

5. Is the sequence of any serious research interest, in general?

Answer 1

$\def\Ker{\operatorname{Ker}}$Let me try to rewrite my answer --- at least, for clarity reasons. Thanks to Pat Devlin and YCor for stimulation.

First, several definitions. A $k$-triangle is a triangle constructed in the described way. We work over $\mathbb F_2$; the $k$-dimensional coordinate space is denoted by $V_k$ (so, any side of a $k$-triangle is a vector in this space). There is a linear operator $\varphi_k\colon V_k\to V_k$ mapping the top vector of a $k$-triangle into its right vector. We have $\varphi_k^3=1$, so $V_k=U_k\oplus W_k$, where $U_k=\Ker(\varphi+1)$ and $W_k=\Ker(\varphi^2+\varphi+1)$ (recall that $1=-1$). Denote $u_k=\dim U_k$ and $w_k=\dim W_k$ (one can see that $w_k$ is always even). For every $v\in V_k$, its $U_k$- and $W_k$-part are $x_u=(\varphi_k^2+\varphi_k+1)x\in U_k$ and $x_w=(\varphi_k^2+\varphi)x\in W_k$ (recall that $x=x_u+x_w$).

We say that vectors in $U_k$ are stable. Vectors starting with $1$ are proper. So, we are interested in the number of proper stable vectors, and it is either $2^{u_k-1}$ or $0$, depeding on whether $U_k$ contains a proper vector or not.

Observation 1. Each vector in $U_k$ has equal first and last coordinates. So, for $k\geq 2$ the space $W_k$ contains a vector with distinct first and last coordinates. The triangles of such vectors have all three sides in $W_k$ and have two ones at the corners. Hence, there are vectors in $W_k$ starting with $1$ and endind with $0$, starting with $0$ and ending with $1$, and also starting and ending with $1$.

Introduce also the following mixing operator. If $a,b\in V_k$, then $\mu_{2k}(a,b)=(a_1,b_1,a_2,b_2,\dots,a_k,b_k)\in V_{2k}$. If $a\in V_{k+1},b\in V_k$, then $\mu_{2k+1}(a,b)=(a_1,b_1,\dots,a_k,b_k,a_{k+1})\in V_{2k+1}$. For $c\in V_n$, denote by $o(c)\in V_{\lceil n/2\rceil}$ and $e(c)\in V_{\lfloor n/2\rfloor}$ the unique vectors such that $\mu_n(o(),e(c))=c$.

The indices will be omitted when they are clear.

Finally, for a vector $c\in V_{k+1}$ we denote by $c\rangle, \langle c\in V_k$ the vector $c$ without the last coordinate and without the first coordinate, respectively. By $\overleftarrow c$ we denote the left cyclic shift of $c$, i.e., $(c_2,c_3,\dots,c_1)$.

Observation 2. The sum of the three digits in the vertices of a $3$-triangle is zero. By induction, the same holds for any $(2^k+1)$-triangle.

Corollary 1. There are no proper stabe vectors in $U_{2^k+1}$.

Corollary 2. Ay $k$-triangle falls into four sparse triangles (of sizes $\lceil k/2\rceil$, $\lfloor k/2\rfloor$, $\lfloor k/2\rfloor$, and $\lceil k/2\rceil-1$).

Corollary 3. (a) Let $a,b\in V_k$, and let $\varphi_{2k}(\mu(a,b))=\mu(c,d)$. Then $c=\varphi_k(b)$ and $d=\varphi_k(a)+c=\varphi_k(a+b)$. The first claim is clear; the second follows from the observation that a sparse $k$-triangle with $d$ on the right has $a+b$ on the top.

(b) Let $a\in V_{k+1}$, $b\in V_k$, and let $\varphi_{2k+1}(\mu(a,b))=\mu(c,d)$. Then $c=\varphi_{k+1}(a)$ and $d=\varphi_k(b+\langle a)=\varphi_k(b)+c\rangle$.

Hugh. Now come to the problem itself.

Assume first that $n=2k$ is even. Then $c=\mu(a,b)\in V_{2k}$ lies in $U_{2k}$ iff $a=\varphi_k(b)$ and $b=\varphi_k(a+b)$, so $b=\varphi_k^2(b)+\varphi_k(b)$, i.e., $b\in W_k$ (and hence $a\in W_k$ as well). Therefore, we have a one-to-one correspondence $W_k\to U_{2k}$ given by $a\mapsto \mu(a,\varphi^2(a))$, and proper vectors correspond to proper ones.

Therefore, $$ u_{2k}=w_k=k-u_k, $$ and the number of proper stable $2k$-vectors is $2^{w_k-1}$ by Observation 1.

Now comes a bit harder case when $n=2k+1$ is odd. A vector $c=\mu(a,b)\in V_{2k+1}$ is stable iff $\varphi(a)=a$ and $\varphi(b)=b+a\rangle$, which rewrites as $a\rangle=(\varphi+1)(b)=\varphi^2(b_w)$. Similarly, we get $\langle a(=\overleftarrow{a\rangle})=\varphi(b_w)$.

So, basicaly we need to search for (proper) $a\in U_{k+1}$ such that $a\rangle\in W_k$; each such will lead to $2^{w_k}$ (proper) stable vectors of the form $\mu(a,b)$, where $b_u=\varphi(a\rangle)$. In other words, we need to find the dimendsion of $W_k\cap (U_{k+1}\rangle)$ and check whether it contains proper vectors.

But in fact $U_{k+1}\rangle \subseteq W_k$. Indeed, take the $(k+1)$-triangle with first row $a$ and remove that first row. We will get the $k$-triangle with top vector $\langle a+a\rangle$, right vector $\langle a$ and left vetor $a\rangle$ which sum up to $0$, as desired.

Hence we get $$ u_{2k+1}=u_{k+1}+u_k. $$

Now the small values yield the dimensions claimed by YCor, namely $u_k=a,a+1,a$ when, respectively, $k=3a,3a+1,3a+2$. Mpreover, each $U_{2k}$ contains a proper vector, and $U_{2k+1}$ does contains a one iff $U_{k+1}$ does. This yields that proper stable vectors exist for all $n$ except for those of the form $2^t+1$, and their number is exactly $2^{u_n-1}$ in all thoese cases. We are done.

Answer 2

OK, let $V_n$ be the vertex set of the following tiling by triangle with $n$ vertices at each large edge. Let me call "standing triangle" a little tiling triangle with a single vertex on the bottom.

For an abelian group $A$, let $A^{V_n}$ be the group of all maps $V_n\to A$. Let $P_n^1(A)$ be its subgroup consisting of those maps summing to zero on each standing triangle. Let $P_n^3(A)$ be the subgroup of $P_n^1(A)$ consisting of those maps that are invariant under $2\pi/3$ rotation.

The perimeter of $V_n$ being the union of its boundary edges, its complement can be identified to $V_{n-3}$. For instance, this picture depicts $\emptyset=V_0\subset V_3\subset V_6$.

$$\begin{matrix} \circ && \circ && \circ && \circ && \circ && \circ\\ &\circ && \circ && \circ && \circ && \circ &\\ &&\circ && \circ && \circ && \circ &&\\ &&& \circ && \circ && \circ &&&\\ &&&& \circ && \circ &&&&\\ &&&&& \circ &&&&& \end{matrix}$$

We proceed to describe $P^i_n(A)$ for each $n$ and $i=1,3$, by passing from $n$ to $n+3$. Hence we start with $n=0,1,2$.

• $n=0$: $V_0$ is empty, so clearly $P_0^1(A)=P_0^3(A)=\{0\}$.
• $n=1$: $V_1$ is a singleton, so clearly $P_0^1(A)=P_0^3(A)=A$.
• $n=2$: $V_2$ is a single standing triangle. Let $A_3=\{a\in A:3a=0\}$. Then $P_0^1(A)$ can be identified to triples of $A$ with sum zero, while $P_0^3(A)=A_3$.

To pass from $n-3$ to $n\ge 3$, we describe the restriction map $P_n^i(A)\to P_{n-3}^i(A)$. Start from $f$ defined on $V_{n-3}$. Then propose some values $a$, $b$, $c$ on the "right" of each extremal vertex:

$$\begin{matrix} &\circ && a && \circ && \circ && \circ &\\ &&\circ && u && v && b &&\\ &&& \circ && w && \circ &&&\\ &&&& c && \circ &&&&\\ &&&&& \circ &&&&& \end{matrix}$$

Then using the sum zero condition, this imposes by propagation values to the right on each edge:

$$\begin{matrix} &x\quad && a && -a-u && a+u-v && y &\\ && c-u+w && u && v && b\quad &&\\ &&& -c-w && w && -b-v &&&\\ &&&& c && b+v-w &&&&\\ &&&&& z &&&&& \end{matrix}$$ $$\text{with}\qquad (x,y,z)=(-a-b-u+v,\;-b-c-v+w,\;-a-c+u-w)$$ (sorry the for the poor alignment of matrix mode)

No further condition is to be fulfilled. This constructs a splitting of the restriction map $P_n^1(A)\to P_{n-3}^1(A)$, which in particular is surjective, and has its kernel isomorphic to $A^3$ (corresponding to $(a,b,c)$). In addition, this is compatible with the rotational symmetry, in which case we have to impose $a=b=c$. Thus, $P_n^1(A)$ is isomorphic to $P_{n-3}(A)\oplus A^3$ and $P_n^3(A)$ is isomorphic to $P_{n-3}(A)\oplus A$ (as abelian groups).

This proves that, for every $n\ge 0$

• $P^1_{3n}(A)$ is isomorphic to $A^{3n}$ and $P^3_{3n}(A)$ is isomorphic to $A^n$;
• $P^1_{3n+1}(A)$ is isomorphic to $A^{3n+1}$ and $P^3_{3n+1}(A)$ is isomorphic to $A^{n+1}$
• $P^1_{3n+2}(A)$ is isomorphic to $A^{3n+2}$ and $P^3_{3n+2}(A)$ is isomorphic to $A_3\oplus A^n$ (hence to $A^n$ if $A$ has no element of order 3).

The method also described an efficient algorithm to generate bases of these, and hence the boundary numbers which are the original objects of study (when $A=\mathbf{F}_2$).

Let us now assume that $A=K$ is a field. The problem asks about the subset $P^3_n(K)_1$, defined with the condition that the extremal vertices are labeled by $1$. This is either empty or an affine hyperplane. If nonempty, this fully describes its dimension as affine subspace (namely $3n\mapsto n-1$, $3n+1\mapsto n$, $3n+2\mapsto n-1$ [or $n$ iff $K$ has characteristic 3].

Note that all this does not say when precisely $P^3_n(K)_1$ is non-empty. When $K$ has characteristic 2 (which boils down to $\mathbf{F}_2$) it was conjectured in the comments that it's empty iff $n=0$ or $n-1$ is a power of $2$.

The description of palindromic solutions $P^6_n(A)$ (i.e., invariant under rotation and reflection) is not obvious and seems also sensitive to the binary expansion of $n$ in some way. However, in characteristic 2 it is clearly equal to $P^6_n(K)_0$, i.e. each extremal vertex is labeled zero, since it forms a standing triangle with two vertices labeled with the same number. That is, $P^6_n(K)_1$ is empty.

---

To be more explicit: the above produces, for $n\ge 3$, a way to pass from $P^3_{n-3}(A)$ to $P^3_n(A)$ explicit in terms of the boundary word. Let me specify to $A=\mathbf{F}_2$ which is the OP's framework: if we have the boundary word $(u_1,\dots,u_{n-3})$, then it has two "successors" of size $n$: $$\begin{matrix}(v_{n-3},&0,& u_1&,&u_1+u_2 &,\dots,& &v_{n-3}&,&v_{n-3})\\ (v_{n-3},&1,&1+u_1&,&1+u_1+u_2 &,\dots,& &1+v_{n-3}&,&v_{n-3}) \end{matrix}$$ In particular, a solution with $1$ on the corners exists in size $n$ if and only if a solution with nonzero sum (that is, $v_{n-3}\neq 0$) —but possibly 0 on the corners— exists in size $n-3$.