13
$\begingroup$

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.enter image description here

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?

$\endgroup$
30
  • 1
    $\begingroup$ Writing at the beginning that xoring= adding mod 2 would save time (I googled to find the definition). $\endgroup$
    – YCor
    May 2, 2020 at 6:33
  • 2
    $\begingroup$ Note that reversing the binary expansion induces an involution on the your set of numbers, whose fixed points are the palindromes, exchanging 11—13, 39—57, 83—101, 91—109, etc. Maybe you can test palindromes until much further than 500000, since a palindrome is governed by twice less digits. $\endgroup$
    – YCor
    May 2, 2020 at 6:47
  • 3
    $\begingroup$ When you work mod 2, addition is the same as subtraction. So the second row gives the first differences of the first row, the third row gives the second differences, and so on. Then you can recover the top row from the left side as a sum of binomial coefficients. E.g., for top row 1101, the left side is 1011, so $1+{n\choose2}+{n\choose3}$ gives $1,1,0,1$, respectively, for $n=0,1,2,3$, respectively (working mod 2). So you can write down what a "special" number is, in terms of binomial coefficients. $\endgroup$ May 2, 2020 at 13:15
  • 7
    $\begingroup$ The nonexistence of palindromic solutions is trivial. Let $a$ be the entry immediately to the right of the $1$ in the upper left corner, let $b$ be the entry immediately below that $1$ (so, the first entry in the 2nd row). For a palindrome, $a=b$. But by construction of the triangle, $1+a=b$. Contradiction. $\endgroup$ May 3, 2020 at 9:41
  • 1
    $\begingroup$ @GerryMyerson, thanks for that nice proof, and the earlier observation. $\endgroup$
    – DSM
    May 3, 2020 at 12:58

2 Answers 2

5
$\begingroup$

$\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.

$\endgroup$
19
  • $\begingroup$ There is an error in your reasoning for the even case. For instance, $n=4$ and $n=6$ and $n=8$ all have the same number of solutions (all have 2 solutions if we require the top left entry to be 1). $n=10$ has 8 solutions (if we require top left entry to be 1). $\endgroup$
    – Pat Devlin
    May 4, 2020 at 14:11
  • $\begingroup$ @PatDevlin: Thanks for pointing that out! I've made some corrections (and introduced one new idea); seems that it is corrected now. Does a new text agree with the numerical data? $\endgroup$ May 4, 2020 at 15:14
  • $\begingroup$ Added some Addendum which makes the things more clear. $\endgroup$ May 4, 2020 at 15:26
  • $\begingroup$ It seems that you haven't still reached the modulo 3 phenomenon. Namely, define $f(3n)=f(3n+2)=2^{n-1}$, $f(3n+1)=2^{n}$. Then the number of solutions, if nonzero, is equal to $f(n)$. (While $2f(n)$ is, for every $n\ge 0$, the number of solutions allowing $0$ on corners.) $\endgroup$
    – YCor
    May 4, 2020 at 15:39
  • $\begingroup$ I@YCor: Yes, in these terms I now know that $2f(k)\cdot 2f(2k)=2^k$ which seems to agree with this formula. An advantage is that I know that for any even $n$ there are solutions with leading ones... Need to think more about an odd case. $\endgroup$ May 4, 2020 at 15:48
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.