Sequences Derived from the Symmetric Powers of {1, 2, …, k}

Po-Yi Huang and Wen-Fong Ke Department of Mathematics National Cheng Kung University Tainan 701 Taiwan

                      pyhuang@ncku.edu.tw
                     wfke@mail.ncku.edu.tw

Abstract For a fixed integer k, we define a sequence A_{k} = (a_{k}(n))_{n≥0} and a corresponding sparse subsequence S_{k} using the cardinality of the n-th symmetric power of the set {1, 2, …, k}. For k ∈ {2, …, 8}, we find recursive formulas for S_{k}, and show that the values a_{k}(0), a_{k}(1), and a_{k}(3) are sufficient for constructing A_{k}.

1 Introduction

Let C and D be finite subsets of ℕ. We recall that the symmetric difference of C and D, denoted by C △D, is the union of C \D and D\C. If C = {c_{1}, …, c_{s}} and D = {d_{1}, …, d_{t}}, both nonempty, we set C ∇ D = c_{1}D △ c_{2}D △ ⋯ △ c_{s}D, where c_{i}D = {c_{i}d_{1}, …, c_{i}d_{t}} for all i. For example,

{1, 2, 3} ∇ {2, 4} = {2, 4} △ {4, 8} △ {6, 12} = {2, 6, 8, 12}.

When either C or D is empty, we put C∇D = ∅. This binary operation ∇ on the finite subsets of ℕ, called the symmetric product, is associative, commutative and distributive over △. We let F denote the set of all finite subsets of ℕ. Consider the map that takes the i-th prime p_{i} to the i-th variable x_{i} of X = {x_{1}, x_{2}, …}. We can extend it in a natural way to a map that takes the natural number t = 2^{s_{1}}3^{s_{2}} ⋯ (s_{i} ≥ 0 with finitely many nonzero s_{i}) to the monomial m_{t} = x_{1}^{s_{1}}x_{2}^{s_{2}} ⋯, then further to a map f that takes the nonempty finite subset T = {t_{1}, …, t_{ℓ}} of ℕ to the multivariate polynomial f(T) = m_{t_{1}} + ⋯ + m_{t_{ℓ}}. Set f(∅) = 0. Then f : F → ℤ_{2}[X] is a ring isomorphism from (F, △, ∇) to the unique factorization domain (ℤ_{2}[X], +, ·) of multivariate polynomials on X = {x_{i} | i ∈ ℕ} over the Galois field of order two.

For k ∈ ℕ, set H_{k} = {1, …, k} and define H_{k}^{∇0} = {1}, H_{k}^{∇1} = H_{k}, H_{k}^{∇2} = H_{k} ∇ H_{k}, and H_{k}^{∇n} = H_{k}^{∇(n−1)} ∇ H_{k} for n > 2. We call H_{k}^{∇n} the n-th symmetric power of H_{k}. It is clear that H_{k}^{∇2} = {1^{2}, …, k^{2}}. In general, we have H_{k}^{∇2^{t}} = {1^{2^{t}}, …, k^{2^{t}}} for t ∈ ℕ. One easily sees that H_{k}^{∇(2n)} = (H_{k}^{∇n})^{∇2} = {x^{2} | x ∈ H_{k}^{∇n}} for all n ∈ ℕ.

In this paper, we consider the sequences A_{k} = (a_{k}(n))_{n≥0}, where a_{k}(n) = |H_{k}^{∇n}|, the cardinality of the n-th symmetric power of H_{k}. Thus, for all k, t ∈ ℕ, we have a_{k}(2^{t}) = |H_{k}^{∇2^{t}}| = k. These sequences arise during the investigation of the minimal distances of certain linear codes (cf. [1, 5, 7, 8]) about which we will not go into detail.

The first few of these sequences can be found in the database The On-Line Encyclopedia of Integer Sequences (OEIS) [10]:

• A_{1} = [1, 1, 1, …] is \underline{A000012};

• A_{2} = [1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, …] is \underline{A001316};

• A_{3} = [1, 3, 3, 9, 3, 9, 9, 27, 3, 9, 9, 27, 9, 27, 27, 81, 3, …] is \underline{A048883};

• A_{4} = [1, 4, 4, 12, 4, 16, 12, 40, 4, 16, 16, 48, 12, 48, 40, 128, 4, …] is \underline{A253064}. These appear as the numbers of ON cells at the n-th generation when certain “odd-rule” cellular automata, with rules 001, 003, 013 and 017, on the square grid are started in generation 0 with a single ON cell at the origin (see [9]).

The sequences A_{k}, k ≥ 5, are not present in the OEIS database. While it is easy to imagine that a_{k}(n) could get as large as possible with n when k ≥ 2, the situation that a_{k}(2^{t}) = k for all t ≥ 0 makes the sequences A_{k} interesting.

We discuss in this article how one can compute A_{k} when 2 ≤ k ≤ 8. We show that a_{k}(n) is closely related to the binary expansion of n. Here, if n = ϵ_{0} + 2ϵ_{1} + ⋯ + 2^{ℓ}ϵ_{ℓ}, where ℓ ≥ 0, and each ϵ_{i} ∈ {0, 1} with ϵ_{ℓ} = 1, then the binary expansion of n is [ϵ_{ℓ}ϵ_{ℓ−1} ⋯ ϵ_{1}ϵ_{0}], and we write (n)_{2} = [ϵ_{ℓ}ϵ_{ℓ−1} ⋯ ϵ_{1}ϵ_{0}].

In the next section, we make an observation that allows us to restrict our attention to the sparse subsequences S_{k} = (a_{k}(2^{n} − 1))_{n≥0} when k ≤ 7. In Section 3, we focus on determining the recursive formula for S_{k} when 2 ≤ k ≤ 8. In the last section, we return to the sequence A_{8}.

2 An observation

Note that every number in H_{k}^{∇n}, 2 ≤ k ≤ 8 and 0 ≤ n, is a product of some powers of 2, 3, 5, and 7.

Lemma 1. Let k, n ∈ ℕ with 1 ≤ k ≤ 7. If n = α + β · 2^{s+1} for some α, β, s ∈ ℕ with α < 2^{s}, then |H_{k}^{∇n}| = |H_{k}^{∇α}| · |H_{k}^{∇β}|.

Proof. We have H_{k}^{∇n} = H_{k}^{∇α} ∇ H_{k}^{∇(β·2^{s+1})}. Let u ∈ H_{k}^{∇α} and v ∈ H_{k}^{∇(β·2^{s+1})}. Then there are e_{i}, f_{i} ∈ ℕ ∪ {0}, 1 ≤ i ≤ 4, such that u = 2^{e_{1}}3^{e_{2}}5^{e_{3}}7^{e_{4}} and v = 2^{f_{1}}3^{f_{2}}5^{f_{3}}7^{f_{4}}. Since k ≤ 7 and α < 2^{s}, we have e_{i} ≤ 2α < 2^{s+1} for each i. On the other hand, we have 2^{s+1} | f_{i} for each i. Hence, we have H_{k}^{∇α} ∩ H_{k}^{∇(β·2^{s+1})} = ∅. Suppose further that u′ = 2^{e′_{1}}3^{e′_{2}}5^{e′_{3}}7^{e′_{4}} ∈ H_{k}^{∇α} and v′ = 2^{f′_{1}}3^{f′_{2}}5^{f′_{3}}7^{f′_{4}} ∈ H_{k}^{∇(β·2^{s+1})} are such that uv = u′v′. Then, for each i, we have e_{i} + f_{i} = e′_{i} + f′_{i}, which is equivalent to f′_{i} − f_{i} = e_{i} − e′_{i}. Since 2^{s+1} | (f′_{i} − f_{i}) and |e_{i} − e′_{i}| < 2^{s+1}, we get f′_{i} − f_{i} = 0. It follows that e_{i} = e′_{i}, and so u = u′ and v = v′. Therefore, we have |H_{k}^{∇n}| = |H_{k}^{∇α}| · |H_{k}^{∇β}| as claimed.

In terms of binary expansions, the numbers α, β, and n in Lemma 1 can be presented as (α)_{2} = [x ⋯ y], (β)_{2} = [b ⋯ d], and (n)_{2} = [(b ⋯ d)(0 ⋯ 0)(x ⋯ y)], where at least one 0 is present in (0 ⋯ 0). Thus, in the cases that k ≤ 7, the lemma implies that if we can compute the sparse subsequence S_{k} = (a_{k}(2^{n} − 1))_{n≥0}, then we can compute every term a_{k}(n) of A_{k} according to the binary expansion of n. For example, if (n)_{2} = [1011011101111], that is n = 11727, then |H_{k}^{∇n}| = |H_{k}^{∇1}| · |H_{k}^{∇3}| · |H_{k}^{∇7}| · |H_{k}^{∇15}| for k ∈ {1, 2, …, 7}.

In general, Lemma 1 does not hold for k ≥ 8. For example, we have |H_{8}^{∇3}| = 48, |H_{8}^{∇8}| = |H_{8}| = 8, and |H_{8}^{∇11}| = 368 ≠ 8 · 48. We will deal with A_{8} separately in the last section.

3 The sparse subsequences

In this section, we consider the sparse subsequences S_{k} = (a_{k}(2^{n} − 1))_{n≥0} where 2 ≤ k ≤ 8. For simplicity, with k fixed, we write θ_{n} = a_{k}(2^{n} − 1) = |H_{k}^{∇(2^{n}−1)}| for n ≥ 0. We have the following recursive formulas for S_{k}.

Proposition 2. For each k, we have θ_{0} = 1 and θ_{1} = k.

(1) If k = 2, then θ_{n+1} = 2θ_{n} for n ≥ 0.

(2) If k = 3, then θ_{n+1} = 3θ_{n} for n ≥ 0.

(3) If k = 4, then θ_{n+2} = 2θ_{n+1} + 4θ_{n} for n ≥ 0.

(4) If k = 5, then θ_{n+2} = 3θ_{n+1} + 6θ_{n} for n ≥ 0.

(5) If k = 6, then θ_{n+1} = 5θ_{n} for n ≥ 1.

(6) If k = 7, then θ_{n+2} = 6θ_{n+1} + θ_{n} for n ≥ 0.

(7) If k = 8, then θ_{n+3} = 7θ_{n+2} − 2θ_{n+1} − 24θ_{n} for n ≥ 0 with θ_{2} = 48.

Together with Lemma 1 and the reduction rules to be derived in Section 4 for k = 8, this proposition gives us the following corollary. Corollary 3. Let n, k ∈ ℕ.

(1) If 2 ≤ k ≤ 7, then a_{k}(n) can be computed from a_{k}(0) = 1 and a_{k}(1) = k.

(2) If k = 8, then a_{k}(n) can be computed from a_{k}(0) = 1, a_{k}(1) = 8, and a_{k}(3) = 48.

The rest of the section is devoted to showing the validity of the formulas in Proposition 2. We start with S_{8} as it provides the best illustration of our approach.

3.1 The case k = 8

For n ≥ 0, the set H_{8}^{∇(2^{n}−1)} is the disjoint union of sets of “chains”. These chains are classified as types A, B, and C. A chain of type A is of the form {x, 2x, 4x, …}; a chain of type B is of the form {x, 4x, 16x, …}; and a chain of type C is just a singleton that is not contained in any chain of type A or type B. These chains are uniquely determined via the following procedure. First, collect all possible chains of type A. After removing the elements of these collected chains from H_{8}^{∇(2^{n}−1)}, collect all possible chains of type B from the remaining elements. After removing the elements of the type B chains thus collected, each of the remaining elements is itself a chain of type C. Let C_{n} be the collection of the chains of H_{8}^{∇(2^{n}−1)}.

For n = 0, we are looking at H_{8}^{∇(2^{0}−1)} = H_{8}^{∇0} = {1}. The chains in C_{0} are

• type A: none;

• type B: none;

• type C: {1}.

For n = 1, we are looking at H_{8}^{∇(2^{1}−1)} = H_{8}. The chains in C_{1} are

• type A: {1, 2, 4, 8} and {3, 6};

• type B: none;

• type C: {5} and {7}.

For n = 2, we are looking at

H_{8}^{∇(2^{2}−1)} = H_{8}^{∇3} = H_{8}^{∇2} ∇ H_{8} = {1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, 6^{2}, 7^{2}, 8^{2}} ∇ {1, 2, 3, 4, 5, 6, 7, 8}. The chains in C_{2} are • type A:

{1, 2},  {3, 6, 12, 24, 48, 96, 192, 384},
{9, 18},  {25, 50, 100, 200},
{27, 54, 108, 216}, {49, 98, 196, 392},
{75, 150},  {144, 288},
{147, 294},  {256, 512};

• type B:

{5, 20, 80, 320}, {7, 28, 112, 448},
{45, 180},  {63, 252};

• type C:

{125}, {175}, {245}, {343}.

Before we continue, let us define some numbers. For a fixed n ≥ 0, we look at C_{n}, and set the numbers b_{n}, c_{n}, u_{n}, v_{n}, and r_{n} as follows:

• b_{n} is the total number of the elements in the chains of type A;

• c_{n} is the number of chains of type A;

• u_{n} is the total number of the elements in the chains of type B;

• v_{n} is the number of chains of type B;

• r_{n} is the total number of elements in the chains of type C. Thus,

b_{0} = c_{0} = u_{0} = v_{0} = 0 and r_{0} = 1;
b_{1} = 6, c_{1} = 2, u_{1} = v_{1} = 0 and r_{1} = 2;
b_{2} = 32, c_{2} = 10, u_{2} = 12, v_{2} = 4 and r_{2} = 4.

We refer to V_{n} = (b_{n}, c_{n}, u_{n}, v_{n}, r_{n})^{t}, a column vector, as the structural vector of H_{8}^{∇(2^{n}−1)}. They can be obtained inductively as we will do next. Note that we have

θ_{n} = |H_{8}^{∇(2^{n}−1)}| = b_{n} + u_{n} + r_{n}.

Assume that n ≥ 2 and that we have obtained the collection of chains C_{n} and the structural vector (b_{n}, c_{n}, u_{n}, v_{n}, r_{n})^{t} of H_{8}^{∇(2^{n}−1)}. We want to get C_{n+1} and the structural vector (b_{n+1}, c_{n+1}, u_{n+1}, v_{n+1}, r_{n+1})^{t} of H_{8}^{∇(2^{n+1}−1)}. Realizing that

H_{8}^{∇(2^{n+1}−1)} = (H_{8}^{∇(2^{n}−1)})^{∇2} ∇ H_{8} = △_{C∈C_{n},D∈C_{1}}(C^{∇2} ∇ D),

we compute all C^{∇2} ∇ D for C ∈ C_{n} and D ∈ C_{1}.

(1) Suppose that x_{i} · {1, 2, 4, …, 2^{ℓ_{i}−1}}, i = 1, 2, …, c_{n}, are the chains of type A in C_{n}. Take x = x_{i} and ℓ = ℓ_{i} (1 ≤ i ≤ c_{n}). Then

{x, 2x, 4x, …, 2^{ℓ−1}x}^{∇2} = x^{2} · {1, 4, 16, 64, …, 2^{2(ℓ−1)}}.

(a) We have

x^{2} · {1, 4, 16, 64, …, 2^{2(ℓ−1)}} ∇ {1, 2, 4, 8}
= x^{2} · {1, 2^{2ℓ}, 2, 2^{2ℓ+1}} = {x^{2}, 2x^{2}} ∪ {2^{2ℓ}x^{2}, 2 · 2^{2ℓ}x^{2}}.

Since ℓ ≥ 2, this yields two distinct chains of type A with length 2. Thus, these symmetric products contribute 4c_{n} to b_{n+1}, and 2c_{n} to c_{n+1}.

(b) We have

x^{2} · {1, 2, 4, …, 2^{ℓ−1}}^{∇2} ∇ {3, 6}
= 3x^{2} · {1, 4, 16, …, 2^{2(ℓ−1)}} ∇ {1, 2}
= 3x^{2} · {1, 2, 4, 8, …, 2^{2ℓ−1}},

a chain of type A with length 2ℓ. Thus, these contribute 2b_{n} to b_{n+1}, and c_{n} to c_{n+1}.

(c) We have

x^{2} · {1, 2, 4, …, 2^{ℓ−1}}^{∇2} ∇ {5} = 5x^{2} · {1, 4, 16, …, 2^{2(ℓ−1)}}

and

x^{2} · {1, 2, 4, …, 2^{ℓ−1}}^{∇2} ∇ {7} = 7x^{2} · {1, 4, 16, …, 2^{2(ℓ−1)}}.

Each of them is a chain of type B with length ℓ. Such symmetric products contribute 2b_{n} to u_{n+1}, and 2c_{n} to v_{n+1}.

(2) Suppose that y_{i} · {1, 4, 16, …, 4^{ℓ′_{i}−1}}, i = 1, 2, …, v_{n}, are the chains of type B in C_{n}. Take y = y_{i} and ℓ′ = ℓ′_{i} (1 ≤ i ≤ v_{n}). Then

{y, 4y, 16y, …, 4^{ℓ′−1}y}^{∇2} = y^{2} · {1, 16, 256, …, 4^{2(ℓ′−1)}}.

(a) As

{y, 4y, 16y, …, 4^{ℓ′−1}y}^{∇2} ∇ {1, 2, 4, 8} = cup_{i=0}^{ℓ′−1}4^{2i}y^{2} · {1, 2, 4, 8}
= y^{2} · {1, 2, 4, 8, 16, 32, …, 2^{4ℓ′−1}},

which is a chain of type A of length 4ℓ′, these contribute 4u_{n} to b_{n+1}, and v_{n} to c_{n+1}.

(b) As

{y, 4y, 16y, …, 4^{ℓ′−1}y}^{2} ∇ {3, 6} = cup_{i=0}^{ℓ′−1}3 · 4^{2i}y^{2} · {1, 2},

which yields ℓ′ chains of type A each of length 2, these contribute 2u_{n} to b_{n+1}, and u_{n} to c_{n+1}.

(c) Each

{y, 4y, 16y, …, 4^{ℓ′−1}y}^{2} ∇ {5} = cup_{i=0}^{ℓ′−1}5 · 4^{2i}y^{2} · {1}

and

{y, 4y, 16y, …, 4^{ℓ′−1}y}^{2} ∇ {7} = cup_{i=0}^{ℓ′−1}7 · 4^{2i}y^{2} · {1}

yields 2ℓ′ chains of type C. Thus, these contribute 2u_{n} to r_{n+1}.

(3) Suppose that {z_{i}}, i = 1, 2, …, r_{n}, are the chains of type C in C_{n}. Take z = z_{i} (1 ≤ i ≤ r_{n}).

(a) Each {z}^{∇2} ∇ {1, 2, 4, 8} = {z^{2}, 2z^{2}, 4z^{2}, 8z^{2}} is a chain of type A with length 4. Thus, these contribute 4r_{n} to b_{n+1}, and r_{n} to c_{n+1}.

(b) Each {z}^{∇2} ∇ {3, 6} = {3z^{2}, 6z^{2}} gives a chain of type A with length 2. Thus, these contribute 2r_{n} to b_{n+1}, and r_{n} to c_{n+1}.

(c) Each of {z}^{∇2} ∇ {5} = {5z^{2}} and {z}^{∇2} ∇ {7} = {7z^{2}} gives a chain of type C. Thus, these contribute 2r_{n} to r_{n+1}.

Summarizing, we get the following system of recursive linear equations expressing b_{n+1}, c_{n+1}, u_{n+1}, v_{n+1}, and r_{n+1} in terms of b_{n}, c_{n}, u_{n}, v_{n}, and r_{n}:

\{ \begin{matrix}b_{n+1} & = & 2b_{n} & +4c_{n} & +6u_{n} & & +6r_{n}, \\ c_{n+1} & = & & 3c_{n} & +u_{n} & +v_{n} & +2r_{n}, \\ u_{n+1} & = & 2b_{n} & & & & , \\ v_{n+1} & = & & 2c_{n} & & & , \\ r_{n+1} & = & & & 2u_{n} & & +2r_{n}. \end{matrix}

Now, we need to clarify that the symmetric products of chains as described above do indeed give us the correct structural vector V_{n+1} of H_{8}^{∇(2^{n+1}−1)} from that of H_{8}^{∇(2^{n}−1)}. Specifically, we need to demonstrate the following. Let C_{1} and C_{2} be two chains in H_{8}^{∇(2^{n}−1)}, and let D_{1} and D_{2} be two chains in H_{8}. If either C_{1} ≠ C_{2} or D_{1} ≠ D_{2}, then

(1) the chains obtained in the symmetric products C = C_{1}^{∇2} ∇ D_{1} and C′ = C_{2}^{∇2} ∇ D_{2} are distinct chains in H_{8}^{∇(2^{n+1}−1)}, and

(2) no longer chains can be formed from these chains.

Since H_{8}^{∇(2^{0}−1)} = H_{8}^{∇0} = {1}, it is clear that the chains in H_{8}^{∇(2^{1}−1)} = H_{8} are exactly produced in this way. Also, one can easily check that the chains in H_{8}^{∇(2^{2}−1)} = H^{∇3} can be produced exactly in this way from those in H_{8}.

Now, if we can show that C ∩ C′ is empty, then (1) is true. Further, if we can show that C ∩ 2C′, C′ ∩ 2C, C ∩ 4C′, and C′ ∩ 4C are all empty, then no concatenating chains to form longer chains are possible, and so (2) holds.

We will show that these are indeed true after we make the following general observation.

Lemma 4. Let C_{1} and C_{2} be two nonempty finite subsets of ℕ, and ℓ ≥ 0. Then the following statements are equivalent.

(1) For j ∈ {0, …, ℓ}, the intersections C_{1} ∩ (2^{j}C_{2}) and C_{2} ∩ (2^{j}C_{1}) are empty.

(2) If 2^{g_{1}}v_{1} ∈ C_{1} and 2^{g_{2}}v_{2} ∈ C_{2}, where g_{i} ≥ 0 and 2 ∤ v_{i} for i = 1 and 2, then either v_{1} ≠ v_{2} or |g_{1} − g_{2}| ≥ ℓ + 1.

Proof. Let 2^{g_{1}}v_{1} ∈ C_{1} and 2^{g_{2}}v_{2} ∈ C_{2}, where g_{i} ≥ 0 and 2 ∤ v_{i} for i = 1 and 2.

Assume (1) and v_{1} = v_{2}. If j ≥ 0, then g_{1} = g_{2}+j implies 2^{g_{1}}v_{1} = 2^{j}·(2^{g_{2}}v_{2}) ∈ C_{1}∩(2^{j}C_{2}), and g_{2} = g_{1} + j implies 2^{g_{2}}v_{2} = 2^{j} · (2^{g_{1}}v_{1}) ∈ C_{2} ∩ (2^{j}C_{1}). By the assumption, these cannot happen for j ≤ ℓ. Hence |g_{1} − g_{2}| ≥ ℓ + 1, and (2) is true.

Conversely, assume (2). If 2^{g_{1}}v_{1} = 2^{g_{2}+j}v_{2} ∈ C_{1} ∩ (2^{j}C_{2}) or 2^{g_{1}+j}v_{1} = 2^{g_{2}}v_{2} ∈ C_{2} ∩ (2^{j}C_{1}), where j ≥ 0, then v_{1} = v_{2}. In such cases, we have j = |g_{1} − g_{2}| ≥ ℓ + 1. Therefore, we get C_{1} ∩ (2^{j}C_{2}) = C_{2} ∩ (2^{j}C_{1}) = ∅ whenever j ∈ {0, 1, …, ℓ}. This is (1).

We now state and prove the desired statement.

Proposition 5. Let C_{1}, C_{2} ∈ C_{n}, and D_{1}, D_{2} ∈ C_{1}. Put C = C_{1}^{∇2} ∇ D_{1} and C′ = C_{2}^{∇2} ∇ D_{2}. If either C_{1} ≠ C_{2} or D_{1} ≠ D_{2}, then C ∩ (2^{i}C′) = C′ ∩ (2^{i}C) = ∅ for i = 0, 1, 2.

Proof. Suppose first that D_{1} ≠ D_{2}. Then (D_{1} \ D_{2}) ∪ (D_{2} \ D_{1}) is not empty, and an odd prime can be found there. Without loss of generality, we may assume that 3 ∈ (D_{1} \ D_{2}). If 2^{e_{1}}3^{e_{2}}5^{e_{3}}7^{e_{4}} ∈ C = C_{1}^{∇2}∇D_{1}, then e_{2} is odd. On the other hand, for i ∈ {0, 1, 2}, if 2^{e′_{1}}3^{e′_{2}}5^{e′_{3}}7^{e′_{4}} ∈ 2^{i}C′ = 2^{i}(C_{2}^{∇2}∇D_{2}), then e′_{2} is even. Hence C ∩ (2^{i}C′) = ∅. Similarly, we have C′ ∩ (2^{i}C) = ∅ for i ∈ {0, 1, 2}.

Suppose that D_{1} = D_{2} = D and C_{1} ≠ C_{2}. Consider u_{1}^{2}d_{1} ∈ C_{1}^{∇2}∇D and u_{2}^{2}d_{2} ∈ C_{2}^{∇2}∇D, where d_{1}, d_{2} ∈ D, u_{1} = 2^{g_{1}}v_{1} ∈ C_{1}, and u_{2} = 2^{g_{2}}v_{2} ∈ C_{2} with g_{1} ≥ 0, g_{2} ≥ 0, and v_{1} and v_{2} being odd. As distinct chains of H_{8}^{∇(2^{n}−1)}, C_{1} and C_{2} satisfy

C_{1} ∩ (2^{i}C_{2}) = ∅ and C_{2} ∩ (2^{i}C_{1}) = ∅ for i ∈ {0, 1, 2}.  (1)

Write d_{1} = 2^{w}v, where w ≥ 0 and 2 ∤ v. Since D is a chain in H_{8} we have d_{2} = 2^{±λ}d_{1} = 2^{±λ+w}v for some λ with 0 ≤ λ ≤ 3. Therefore,

u_{1}^{2}d_{1} = 2^{2g_{1}+w}v_{1}^{2}v and u_{2}^{2}d_{2} = 2^{2g_{2}±λ+w}v_{2}^{2}v.

Now, if v_{1}^{2}v = v_{2}^{2}v, then v_{1} = v_{2}, and so |g_{1} − g_{2}| ≥ 3 by Lemma 4. Hence

|(2g_{1} + w) − (2g_{2} ± λ + w)| ≥ 2 · |g_{1} − g_{2}| − |λ| ≥ 3.

Again, by Lemma 4, we have C ∩ (2^{i}C′) = C′ ∩ (2^{i}C) = ∅ for i = 0, 1, and 2.

Expressing the linear recursive system (3.1) in matrix form, we have V_{n+1} = MV_{n}, where

M = (\begin{matrix}2 & 4 & 6 & 0 & 6 \\ 0 & 3 & 1 & 1 & 2 \\ 2 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 2 \end{matrix}) and V_{n} = (\begin{matrix}b_{n} \\ c_{n} \\ u_{n} \\ v_{n} \\ r_{n} \end{matrix}) , n = 0, 1, 2, …, with V_{0} = (\begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 1 \end{matrix}) .  (2)

Setting U = (1, 0, 1, 0, 1), we have

θ_{n+1} = b_{n+1} + u_{n+1} + r_{n+1} = UV_{n+1} = UMV_{n}.

Now, the minimal polynomial of M is X^{2}(X^{3} − 7X^{2} + 2X + 24), and so we have

U(M^{3} − 7M^{2} + 2M + 24I)M^{2} = 0.

A direct check shows that

UM = (4, 4, 8, 0, 8) ,
UM^{2} = (24, 28, 44, 4, 48) ,
UM^{3} = (136, 188, 268, 28, 296) ,

and that

UM^{3} − 7UM^{2} + 2UM + 24U = 0.  (3)

Therefore, for n ≥ 0, we have

θ_{n+3} = UM^{3}V_{n} = (7UM^{2} − 2UM − 24U)V_{n} = 7θ_{n+2} − 2θ_{n+1} − 24θ_{n}.  (4)

Remark 6. We can tabulate the above computations:

{1, 2, 4, 8} {3, 6} {5}, {7}  b_{n+1}  c_{n+1} u_{n+1} v_{n+1} r_{n+1} (b_{n}, c_{n}) A_{ℓ}  2A_{2}  A_{2ℓ}  2B_{ℓ}  4c_{n} + 2b_{n}  3c_{n}  2b_{n} 2c_{n} (u_{n}, v_{n}) B_{ℓ}  A_{4ℓ}  ℓA_{2}  2ℓC 4u_{n} + 2u_{n} v_{n} + u_{n}  2u_{n} (r_{n}) C  A_{4}  A_{2}  2C  6r_{n}  2r_{n}  2r_{n} .

Here, in the table, we use A_{ℓ} and B_{ℓ} to indicate a chain of type A and type B of length ℓ, respectively; and we use C to indicate a chain of a singleton. Also, we use 2A_{ℓ} to indicate two disjoint chains of type A with length ℓ, etc. The (b_{n}, c_{n}), (u_{n}, v_{n}), and (r_{n}) in the first column are to remind the variables used for counting in the respective rows, and the break-downs are shown in the columns to the right.

For D ∈ {{1, 2, 4, 8}, {3, 6}, {5}, {7}}, the first row records the pattern for the symmetric products A_{ℓ}^{∇2} ∇ D, the second row records the pattern for the symmetric products B_{ℓ}^{∇2} ∇ D, and the last row records the pattern for the symmetric products C^{∇2} ∇ D. The columns of b_{n+1}, c_{n+1}, u_{n+1}, v_{n+1}, r_{n+1} show us the recursive equations we have seen above. For example, the column of b_{n+1} reads b_{n+1} = 4c_{n} + 2b_{n} + 4u_{n} + 2u_{n} + 6r_{n} = 2b_{n} + 4c_{n} + 6u_{n} + 6r_{n}. The corresponding matrix M of the system of linear equations can then be written down easily.

3.2 The case k = 2, 3, 4, 5, 6, 7

Recall that H_{k}^{∇(2^{n+1}−1)} = (H_{k}^{∇(2^{n}−1)})^{∇2} ∇ H_{k} = △_{i=1}^{k}i(H_{k}^{∇(2^{n}−1)})^{∇2}. Since the elements in (H_{2}^{∇(2^{n}−1)})^{∇2} and in (H_{3}^{∇(2^{n}−1)})^{∇2} are squares for all n ≥ 1, and those in 2(H_{2}^{∇(2^{n}−1)})^{∇2}, 2(H_{3}^{∇(2^{n}−1)})^{∇2}, and 3(H_{3}^{∇(2^{n}−1)})^{∇2} are not, we have

(H_{2}^{∇(2^{n}−1)})^{∇2} ∩ (2(H_{2}^{∇(2^{n}−1)})^{∇2}) = ∅,
(H_{3}^{∇(2^{n}−1)})^{∇2} ∩ (2(H_{3}^{∇(2^{n}−1)})^{∇2}) = ∅,
(H_{3}^{∇(2^{n}−1)})^{∇2} ∩ (3(H_{3}^{∇(2^{n}−1)})^{∇2}) = ∅.

Also it is clear that

(2(H_{3}^{∇(2^{n}−1)})^{∇2}) ∩ (3(H_{3}^{∇(2^{n}−1)})^{∇2}) = ∅.

Therefore, for k = 2 and 3, and n ≥ 1, we have

θ_{n+1} = |H_{k}^{∇(2^{n+1}−1)}| = |△_{i=1}^{k}i(H_{k}^{∇(2^{n}−1)})^{∇2}|

= ∑_{i=1}^{k} |i(H_{k}^{∇(2^{n}−1)})^{∇2}|

= k · |(H_{k}^{∇(2^{n}−1)})^{∇2}| = |H_{k}^{∇(2^{n}−1)}| · |H_{k}| = kθ_{n}.  (5)

As θ_{0} = 1, (5) holds for n ≥ 0.

For each k ∈ {4, 5, 6, 7} we analyze H_{k} and compute the symmetric products C^{∇2} ∇ D of the chains C of H_{k}^{∇(2^{n}−1)} and the chains D of H_{k} to produce a table just like we did for H_{8}^{∇(2^{n+1}−1)} in Remark 6. It turns out that in these cases we only need to collect chains of types A and C. Namely, for each H_{k}^{∇(2^{n}−1)}, k ∈ {4, 5, 6, 7}, and n ∈ ℕ, we would collect all possible chains of type A. After removing the elements of these collected chains, each of the remaining elements gives us a chain of type C. The structural vector of H_{k}^{∇(2^{n}−1)} is then set to be V_{n} = (b_{n}, c_{n}, r_{n})^{t}, where b_{n} is the total number of the elements in the chains of type A, c_{n} is the number of chains of type A, and r_{n} is the total number of elements in the chains of type C.

We also need to justify that when the chains C_{1} and C_{2} of H_{k}^{∇(2^{n}−1)} are distinct and/or the chains D_{1} and D_{2} of H_{k} are distinct, the chains produced in the symmetric product C_{1}^{∇2} ∇ D_{1} and those produced in C_{2}^{∇2} ∇ D_{2} are disjoint and cannot be concatenated to form longer chains. The following proposition similar to Proposition 5 provides us the justification.

Proposition 7. Let k ∈ {4, 5, 6, 7}. Let C_{1} and C_{2} be chains of H_{k}^{∇(2^{n}−1)}, and D_{1} and D_{2} that of H_{k}. Put C = C_{1}^{∇2} ∇ D_{1} and C′ = C_{2}^{∇2} ∇ D_{2}. If either C_{1} ≠ C_{2} or D_{1} ≠ D_{2}, then for i = 0 and 1, C ∩ (2^{i}C′) = C′ ∩ (2^{i}C) = ∅.

To prove Proposition 7, one can use the proof of Proposition 5 as a template. The only changes needed are to adjust the range of λ from 0 ≤ λ ≤ 3 to 0 ≤ λ ≤ 2 (as 8 is not present in H_{k}), change the inequality |g_{1} − g_{2}| ≥ 3 to |g_{1} − g_{2}| ≥ 2, and apply Lemma 4 to obtain the desired conclusion from the inequality

|(2g_{1} + w) − (2g_{2} ± λ + w)| ≥ 2 · |g_{1} − g_{2}| − |λ| ≥ 2.

Thus, for each k = 4, 5, 6, 7, M is a 3 × 3 matrix. The size θ_{n+1} = |H_{k}^{∇(2^{n+1}−1)}| satisfies θ_{n+1} = UMV_{n}, where U = (1, 0, 1) and V_{n} = (b_{n}, c_{n}, r_{n})^{t}. Therefore, to get the recursive formula for θ_{k}, it suffices to write down the table of the symmetric products of the chains, the matrix M, the minimal polynomial of M and the polynomial P in M with UP (M) = 0.

3.2.1 k = 4

The table of the symmetric products of the chains reads

\begin{aligned}& & \{1, 2, 4\} & \{3\} & b_{n+1} & c_{n+1} & r_{n+1} \\ (b_{n}, c_{n}) & A_{ℓ} & 2A_{2}, (ℓ − 2)C & ℓC & 4c_{n} & 2c_{n} & 2b_{n} − 2c_{n} \\ (r_{n}) & C & A_{3} & C & 3r_{n} & r_{n} & r_{n} \end{aligned} .

The corresponding matrix M = (\begin{matrix}0 & 4 & 3 \\ 0 & 2 & 1 \\ 2 & −2 & 1 \end{matrix}) has the minimal polynomial

X^{3} − 3X^{2} − 2X + 4 = (X − 1)(X^{2} − 2X − 4).

We have U(M^{2} − 2M − 4I) = 0, and so for n ≥ 0,

θ_{n+2} = 2θ_{n+1} + 4θ_{n}.

3.2.2 k = 5

The table of the symmetric products of the chains reads

\begin{aligned}& & \{1, 2, 4\} & \{3\}, \{5\} & b_{n+1} & c_{n+1} & r_{n+1} \\ (b_{n}, c_{n}) & A_{ℓ} & 2A_{2}, (ℓ − 2)C & 2ℓC & 4c_{n} & 2c_{n} & 3b_{n} − 2c_{n} \\ (r_{n}) & C & A_{3} & 2C & 3r_{n} & r_{n} & 2r_{n} \end{aligned} .

The corresponding matrix M = (\begin{matrix}0 & 4 & 3 \\ 0 & 2 & 1 \\ 3 & −2 & 2 \end{matrix}) has the minimal polynomial

X^{3} − 4X^{2} − 3X + 6 = (X − 1)(X^{2} − 3X − 6).

We have U(M^{2} − 3M − 6I) = 0, and so for n ≥ 0, θ_{n+2} = 3θ_{n+1} + 6θ_{n}.

3.2.3 k = 6 The table of the symmetric products of the chains reads

{3, 6}  {1, 2, 4}  {5}  b_{n+1}  c_{n+1}  r_{n+1} (b_{n}, c_{n}) A_{ℓ} A_{2ℓ} 2A_{2}, (ℓ − 2)C ℓC 2b_{n} + 4c_{n} 3c_{n} 2b_{n} − 2c_{n} (r_{n}) C A_{2}  A_{3}  C  5r_{n}  2r_{n}  r_{n} .

The corresponding matrix M = (\begin{matrix}2 & 4 & 5 \\ 0 & 3 & 2 \\ 2 & −2 & 1 \end{matrix}) has the minimal polynomial

X^{3} − 6X^{2} + 5X = X(X − 1)(X − 5).

We have U(M^{2} − 5M) = 0, and so for n ≥ 1, θ_{n+1} = 5θ_{n}.

3.2.4 k = 7 The table of the symmetric products of the chains reads

{3, 6}  {1, 2, 4}  {5}, {7}  b_{n+1}  c_{n+1}  r_{n+1} (b_{n}, c_{n}) A_{ℓ} A_{2ℓ} 2A_{2}, (ℓ − 2)C 2ℓC 2b_{n} + 4c_{n} 3c_{n} 3b_{n} − 2c_{n} (r_{n}) C A_{2}  A_{3}  2C  5r_{n}  2r_{n}  2r_{n} .

The corresponding matrix M = (\begin{matrix}2 & 4 & 5 \\ 0 & 3 & 2 \\ 3 & −2 & 2 \end{matrix}) has the minimal polynomial

X^{3} − 7X^{2} + 5X + 1 = (X − 1)(X^{2} − 6X − 1).

We have U(M^{2} − 6M − I) = 0, and so for n ≥ 0, θ_{n+2} = 6θ_{n+1} + θ_{n}.

4 The sequence A_{8}

Recall that for the sparse subsequence S_{8} = (θ_{n})_{n≥0}, where θ_{n} = |H_{8}^{∇(2^{n}−1)}|, we associate a structural vector V_{n} = (b_{n}, c_{n}, u_{n}, v_{n}, r_{n})^{t} with each H_{8}^{∇(2^{n}−1)}, so that θ_{n} = UMV_{n} for all n ≥ 0 with the vector U = (1, 0, 1, 0, 1) and the 5 × 5 matrix M in (2). We can extend this idea to A_{8} in order to get every a_{8}(n) = |H_{8}^{∇n}|, n ≥ 0.

For each n, we again collect the chains of types A, B and C in H_{8}^{∇n}, and define the structural vector Λ_{n} of H_{8}^{∇n} to be (b_{n}, c_{n}, u_{n}, v_{n}, r_{n})^{t}. Note that the same variables b_{n}, c_{n}, u_{n}, v_{n}, and r_{n} are used here. Yet they are not the same in the indices as we have used them when dealing with the sparse subsequences S_{k}.

Now, the structural vector of H_{8}^{∇0} = {1} is Λ_{0} = (0, 0, 0, 0, 1)^{t} = V_{0}. Next, with H_{8}^{∇1} =

(H_{8}^{∇(2^{0}−1)})^{2} ∇H_{8}, we apply the matrix M in (2) to Λ_{0} to get Λ_{1} (which is V_{1} in this case). Thus, Λ_{1} = MΛ_{0} = (6, 2, 0, 0, 2)^{t}. To get Λ_{2}, the structural vector of H_{8}^{∇2}, we need another matrix for symmetric squaring.

Let n ≥ 1. Suppose that we have obtained the collection of chains C of H_{8}^{∇n} and the structural vector Λ_{n} = (b_{n}, c_{n}, u_{n}, v_{n}, r_{n})^{t}. For a type A chain of length ℓ, say C = {x, 2x, …, 2^{ℓ}x}, we have C^{∇2} = {x^{2}, 4x^{2}, …, 4^{ℓ−1}x^{2}}, which is a type B chain of length ℓ in H_{8}^{∇2n}. For a type B chain of length ℓ, say C = {x, 4x, …, 4^{ℓ−1}x}, we have C^{∇2} = {x^{2}, 16x^{2}, …, 16^{ℓ−1}x^{2}} = ∪_{i=0}^{ℓ−1}{16^{i}x^{2}}, which is the union of ℓ type C chains in H_{8}^{∇2n}. Obviously, {x}^{∇2} = {x^{2}} for every type C chain {x} in C. This is a type C chain in H_{8}^{∇2n}. Thus, the table for symmetric squaring is as follows:

\begin{aligned}& C & C^{∇2} & b_{2n} & c_{2n} & u_{2n} & v_{2n} & r_{2n} \\ (b_{n}, c_{n}) & A_{ℓ} & B_{ℓ} & & & b_{n} & c_{n} \\ (u_{n}, v_{n}) & B_{ℓ} & ℓC & & & & & u_{n} \\ (r_{n}) & C & C & & & & & r_{n} \end{aligned} .

The corresponding matrix W is

W = (\begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix}) .

We have Λ_{2n} = W Λ_{n} and, in particular, Λ_{2} = W Λ_{1} = (W M)Λ_{0}.

Lemma 8. Let n ≥ 0 be arbitrary, and suppose that (n)_{2} = [ϵ_{ℓ}ϵ_{ℓ−1} ⋯ ϵ_{1}ϵ_{0}]. Then

Λ_{n} = E_{0}E_{1} ⋯ E_{ℓ−1}E_{ℓ}Λ_{0},

where, for each i, E_{i} = M if ϵ_{i} = 1, and E_{i} = W if ϵ_{i} = 0.

Proof. The result holds for ℓ = 0 and ℓ = 1 as we have just seen. Let ℓ ≥ 2. Take m ∈ ℕ with (m)_{2} = [ϵ_{ℓ}ϵ_{ℓ−1} ⋯ ϵ_{1}]. Assume that Λ_{m} = E_{1} ⋯ E_{ℓ−1}E_{ℓ}Λ_{0} with E_{i} = M if ϵ_{i} = 1, and E_{i} = W if ϵ_{i} = 0.

If ϵ_{0} = 0, then n = 2m. In this case, we have H_{8}^{∇n} = H_{8}^{∇(2m)} = (H_{8}^{∇m})^{∇2} and so Λ_{n} = W Λ_{m}.

If ϵ_{0} = 1, then n = 2m + 1. In this case, we have

H_{8}^{∇n} = H_{8}^{∇(2m+1)} = H_{8}^{∇(2m)} ∇ H_{8} = (H_{8}^{∇m})^{∇2} ∇ H_{8},

and so Λ_{n} = MΛ_{m}.

Therefore, by the induction hypothesis, we have

Λ_{n} = E_{0}E_{1} ⋯ E_{ℓ−1}E_{ℓ}Λ_{0}

where E_{i} = M if ϵ_{i} = 1, and E_{i} = W if ϵ_{i} = 0.

Recall that U = (1, 0, 1, 0, 1), and |H_{8}^{∇n}| = UΛ_{n} for all n ≥ 0. We shall derive some reduction rules to help to compute every |H_{8}^{∇n}|, n ∈ ℕ. We already know that

|H_{8}^{∇2m}| = |H_{8}^{∇m}| for all m ∈ ℕ.  (6)

Notice that

W^{2} = Λ_{0}U,

and we have the following result similar to Lemma 1.

Lemma 9. If n = α + β · 2^{s+2} for some α, β, s ∈ ℕ with α < 2^{s}, then

|H_{8}^{∇n}| = |H_{8}^{∇α}| · |H_{8}^{∇β}|.  (7)

Proof. Let (α)_{2} = [x ⋯ z] and (β)_{2} = [b ⋯ d]. Then (n)_{2} = [(b ⋯ d)(00 ⋯ 0)(x ⋯ z)], where there are at least two 0’s between (b ⋯ d) and (x ⋯ z). Let C_{1} and C_{2} be the products of M’s and W ’s such that Λ_{α} = C_{1}Λ_{0} and Λ_{β} = C_{2}Λ_{0}. Then for some ℓ ≥ 0, we have

|H_{8}^{∇n}| = UΛ_{n} = UC_{1}W^{ℓ+2}C_{2}Λ_{0}
= UC_{1}Λ_{0}UW^{ℓ}C_{2}Λ_{0}
= (UΛ_{α})(UΛ_{2^{ℓ}β})
= |H_{8}^{∇α}| · |H_{8}^{∇(2^{ℓ}β)}|
= |H_{8}^{∇α}| · |(H_{8}^{∇β})^{∇2^{ℓ}}| = |H_{8}^{∇α}| · |H_{8}^{∇β}|.

Next, we collect some useful facts about M and W.

Lemma 10. With M, W, U, and Λ_{0} as above, we have (1) UΛ_{0} = 1;

(2) UW = U;

(3) UMW = 8U;

(4) UM^{2}W = UM + 40U. Consequently, if C is a product of M’s and W ’s, then UC = U(pM^{2} + qM + rI) for some p, q, r ∈ ℤ. Proof. The four identities can be checked directly. Combining (2)–(4) and the fact that UM^{3} = 7UM^{2} − 2UM − 24U (see (3)), we infer that UC = U(pM^{2} + qM + rI) for some p, q, r ∈ ℤ as claimed. Lemma 11. If (n)_{2} = [(b ⋯ d)01] and (m)_{2} = [b ⋯ d], then

|H_{8}^{∇n}| = 8 · |H_{8}^{∇m}|.  (8)

Proof. As Λ_{n} = MW Λ_{m}, we have, by Lemma 10(3), |H_{8}^{∇n}| = UΛ_{n} = UMW Λ_{m} = 8UΛ_{m} = 8 · |H_{8}^{∇m}|.

Lemma 12. If (n)_{2} = [(b ⋯ d)011], (m_{1})_{2} = [b ⋯ d1] and (m_{2})_{2} = [b ⋯ d], then

|H_{8}^{∇n}| = |H_{8}^{∇m_{1}}| + 40 · |H_{8}^{∇m_{2}}|.  (9)

Proof. As Λ_{n} = M^{2}W Λ_{m_{2}}, we have, by Lemma 10(4),

|H_{8}^{∇n}| = UΛ_{n} = UM^{2}W Λ_{m_{2}} = (UM + 40U)Λ_{m_{2}}
= UMΛ_{m_{2}} + 40UΛ_{m_{2}} = UΛ_{m_{1}} + 40UΛ_{m_{2}} = |H_{8}^{∇m_{1}}| + 40 · |H_{8}^{∇m_{2}}|.

Lemma 13. Let (n)_{2} = [(b ⋯ d)111(x ⋯ z)]. With

(m_{1})_{2} = [(b ⋯ d)11(x ⋯ z)], (m_{2})_{2} = [(b ⋯ d)1(x ⋯ z)], and (m_{3})_{2} = [(b ⋯ d)(x ⋯ z)], we have

|H_{8}^{∇n}| = 7 · |H_{8}^{∇m_{1}}| − 2 · |H_{8}^{∇m_{2}}| − 24 · |H_{8}^{∇m_{3}}|,  (10)

Proof. Let α ≥ 0 and β ≥ 0 be such that (α)_{2} = [x ⋯ z] and (β)_{2} = [b ⋯ d], and let C be the products of M’s and W ’s such that Λ_{α} = CΛ_{0}. Then Λ_{n} = CM^{3}Λ_{β}, Λ_{m_{1}} = CM^{2}Λ_{β}, Λ_{m_{2}} = CMΛ_{β}, and Λ_{m_{3}} = CΛ_{β}. By Lemma 10, we have UC = U(pM^{2} + qM + rI) for some p, q, r ∈ ℤ. Let D = pM^{2} + qM + rI. From (3), we get

|H_{8}^{∇n}| = UΛ_{n} = UCM^{3}Λ_{β}
= UDM^{3}Λ_{β}
= UM^{3}DΛ_{β}
= U(7M^{2} − 2M − 24I)DΛ_{β}
= 7UM^{2}DΛ_{β} − 2UMDΛ_{β} − 24UDΛ_{β}
= 7UDM^{2}Λ_{β} − 2UDMΛ_{β} − 24UDΛ_{β}
= 7UCM^{2}Λ_{β} − 2UCMΛ_{β} − 24UCΛ_{β}
= 7UΛ_{m_{1}} − 2UΛ_{m_{2}} − 24UΛ_{m_{3}}
= 7 · |H_{8}^{∇m_{1}}| − 2 · |H_{8}^{∇m_{2}}| − 24 · |H_{8}^{∇m_{3}}|.

We are in a position to show that we can get every |H_{8}^{∇n}|, n ∈ ℕ, with just |H_{8}^{∇0}|, |H_{8}^{∇1}| and |H_{8}^{∇3}| by applying (6)–(9) repeatedly.

Let S be the set of all n ≥ 0, such that none of the rules (6), (7), (8) and (9) applies. In particular, if n ∈ S, then the binary expansion (n)_{2}, when read from the higher bits to the lower bits, does not have 00 or 111 anywhere, and does not end with 0 or 01.

• If (n)_{2} has just one bit, then (n)_{2} is either (0)_{2} = [0], or (1)_{2} = [1]. We have |H_{8}^{∇0}| = 1 and |H_{8}^{∇1}| = 8.

• If (n)_{2} has two bits, then (n)_{2} has to be (3)_{2} = [11]. We have |H_{8}^{∇3}| = 48.

So we have {0, 1, 3} ⊆ S.

Proposition 14. The set S is exactly {0, 1, 3}.

Proof. As (4)_{2} = [100], (5)_{2} = [101], (6)_{2} = [110], and (7)_{2} = [111], no integers with a 3 bit binary expansion belong to S.

Let n ∈ S. Suppose that (n)_{2} has at least 4 bits. Then the last three bits of (n)_{2} has to be 011. So (n)_{2} = [(b ⋯ d)011]. But then (9) applies, contradicting to that n ∈ S. Therefore, (n)_{2} has at most 3 bits, and we are done.

Now Corollary 3(2) follows.

Example 15. (1) The identity (9) gives us

|H_{8}^{∇11}| = |H_{8}^{∇3}| + 40 · |H_{8}^{∇1}| = 368
since (11)_{2} = [1011], (3)_{2} = [11], and (1)_{2} = [1].

(2) Using (9) again, we get

|H_{8}^{∇27}| = |H_{8}^{∇7}| + 40 · |H_{8}^{∇3}| = |H_{8}^{∇7}| + 1920

since (27)_{2} = [11011], (7)_{2} = [111], and (3)_{2} = [11]. It follows from (10) that

|H_{8}^{∇7}| = 7 · |H_{8}^{∇3}| − 2 · |H_{8}^{∇1}| − 24 · |H_{8}^{∇0}| = 296.

Hence |H_{8}^{∇27}| = 2216. We give two more reduction rules which can be useful for computing |H_{8}^{∇n}|. Here is the

first one. Lemma 16. If (n)_{2} = [(b ⋯ d)011011], (m_{1})_{2} = [(b ⋯ d)011] and (m_{2})_{2} = [b ⋯ d], then

|H_{8}^{∇n}| = 47 · |H_{8}^{∇m_{1}}| − 40 · |H_{8}^{∇m_{2}}|.  (11)

Proof. We have

|H_{8}^{∇n}| = UM^{2}W M^{2}W Λ_{m_{2}}

= (UM + 40U)M^{2}W Λ_{m_{2}} = UM^{3}W Λ_{m_{2}} + 40UM^{2}W Λ_{m_{2}} = (7UM^{2} − 2UM − 24UI)W Λ_{m_{2}} + 40UM^{2}W Λ_{m_{2}} = 47UM^{2}W Λ_{m_{2}} − 2UMW Λ_{m_{2}} − 24UW Λ_{m_{2}} = 47UΛ_{m_{1}} − 16UΛ_{m_{2}} − 24UΛ_{m_{2}} = 47UΛ_{m_{1}} − 40UΛ_{m_{2}} = 47 · |H_{8}^{∇m_{1}}| − 40 · |H_{8}^{∇m_{2}}|.

The second one requires the following facts about W M, which can be checked directly. We note that the minimal polynomial of W M is X^{4} − 9X^{3} + 8X^{2}, and so

UW M((W M)^{2} − 9W M + 8I) = 0.  (12)

Since UW = U, (12) is reduced to

UM((W M)^{2} − 9W M + 8I) = 0.  (13)

Furthermore, it is also true that

UM^{2}((W M)^{2} − 9W M + 8I) = 0.  (14)

Although UM^{3}((W M)^{2} − 9W M + 8I) ≠ 0, we still have

UM^{3}((W M)^{2} − 9W M + 8I)Λ_{0} = 0.  (15)

Lemma 17. Let n, m_{1}, m_{2} ∈ ℕ. If one of the following holds

(1) (n)_{2} = [(b ⋯ d)101011], (m_{1})_{2} = [(b ⋯ d)1011] and (m_{2})_{2} = [(b ⋯ d)11],

(2) (n)_{2} = [10101(x ⋯ z)], (m_{1})_{2} = [101(x ⋯ z)], and (m_{2})_{2} = [1(x ⋯ z)],

then

|H_{8}^{∇n}| = 9 · |H_{8}^{∇m_{1}}| − 8 · |H_{8}^{∇m_{2}}|.  (16)

Proof.

(1) Let α ≥ 0 with (α)_{2} = [b ⋯ d]. We have

|H_{8}^{∇m_{2}}| = UM^{2}Λ_{α},
|H_{8}^{∇m_{1}}| = UM^{2}W MΛ_{α},

and

|H_{8}^{∇n}| = UM^{2}(W M)^{2}Λ_{α}.

Together with (14), this gives

|H_{8}^{∇n}| − 9 · |H_{8}^{∇m_{1}}| + 8 · |H_{8}^{∇m_{2}}| = UM^{2}((W M)^{2} − 9W M + 8I))Λ_{α} = 0.

(2) Let β ≥ 0 with (β)_{2} = [x ⋯ z]. Let C be the product of M’s and W ’s such that Λ_{β} = CΛ_{0}. We have |H_{8}^{∇m_{2}}| = UCMΛ_{0}, |H_{8}^{∇m_{1}}| = UCMW MΛ_{0} and |H_{8}^{∇n}| = UCM(W M)^{2}Λ_{0}. Let p, q, r ∈ ℤ such that UC = pUM^{2} + qUM + rU. Then

|H_{8}^{∇n}| − 9 · |H_{8}^{∇m_{1}}| + 8 · |H_{8}^{∇m_{2}}|
= UCM((W M)^{2} − 9W M + 8I)Λ_{0}
= U(pM^{2} + qM + rI)M((W M)^{2} − 9W M + 8I)Λ_{0}
= pUM^{3}((W M)^{2} − 9W M + 8I)Λ_{0}
+ qUM^{2}((W M)^{2} − 9W M + 8I)Λ_{0}
+ rUM((W M)^{2} − 9W M + 8I)Λ_{0}.

According to (13)–(15), the last three terms are all zero. We are done.

Here is an example of |H_{8}^{∇n}| with a bit larger n.

Example 18. Let us compute |H_{8}^{∇n}| where (n)_{2} = (11101011011), so n = 1883. First of all, we apply (10) with (m_{1})_{2} = [11101011] and (m_{2})_{2} = [11101] to get

|H_{8}^{∇n}| = 47 · |H_{8}^{∇m_{1}}| − 40 · |H_{8}^{∇m_{2}}|,

Next, we put together (16) and (8) with (β_{1})_{2} = [111011], (β_{2})_{2} = [1111], and (γ)_{2} = [111], and we get

|H_{8}^{∇m_{1}}| = 9 · |H_{8}^{∇β_{1}}| − 8 · |H_{8}^{∇β_{2}}| and |H_{8}^{∇m_{2}}| = 8 · |H_{8}^{∇γ}|.

Lastly, we infer from (10) that

|H_{8}^{∇β_{1}}| = 7 · |H_{8}^{∇27}| − 2 · |H_{8}^{∇11}| − 24 · |H_{8}^{∇3}| = 13624,
|H_{8}^{∇β_{2}}| = 7 · |H_{8}^{∇7}| − 2 · |H_{8}^{∇3}| − 24 · |H_{8}^{∇1}| = 1784,
|H_{8}^{∇γ}| = |H_{8}^{∇7}| = 296,

and so |H_{8}^{∇m_{1}}| = 108344 and |H_{8}^{∇m_{2}}| = 2368. Therefore, |H_{8}^{∇n}| = 4997448.

When applying the above rules for computing |H_{8}^{∇n}|, there is no particular order that one have to follow. Some orders could be more efficient than others when applied in specific cases. Still, one can design certain general algorithm to compute |H_{8}^{∇n}|.

Finally, we remark that we do not have any formula for A_{k} and S_{k} when k ≥ 9. The approach using chains like above fails since new types of chains need to be introduced, e.g., chains of the type {x, 3x, 9x, …}, and they may not be disjoint from the chains of other types.

5 Acknowledgments

The authors like to thank the reviewer and the editor for their careful reading and comments to improve the clarity and the readability of the paper.

References

[1] A. E. Caicedo, T. A. C. Chartier, and P. P. Pach, Coloring the n-smooth numbers with n colors, Electron. J. Combin. 28 (2021), Paper 1.34.

[2] S. B. Ekhad, N. J. A. Sloane, and D. Zeilberger, Odd-rule cellular automata on the square grid, arxiv preprint arXiv:1503.04249 [math.CO], 2015. Available at https://

    arxiv.org/abs/1503.04249.

[3] S. B. Ekhad, N. J. A. Sloane, and D. Zeilberger, A meta-algorithm for creating fast algorithms for counting ON cells in odd-rule cellular automata, arxiv preprint arXiv:1503.01796 [math.CO], 2015. Available at https://arxiv.org/abs/1503.01796.

[4] S. B. Ekhad, N. J. A. Sloane, and D. Zeilberger, A meta-algorithm for creating fast algorithms for counting ON cells in odd-rule cellular automata (Maple

    package), 2015. Available at https://www.math.rutgers.edu/~zeilberg/mamarim/
    mamarimhtml/CAcount.html.

[5] P.-Y. Huang, W.-F. Ke, and G. F. Pilz, The cardinality of some symmetric differences, Proc. Amer. Math. Soc. 138 (2010), 787–797.

[6] T. Khovanova, There are no coincidences, arxiv preprint arXiv:1410.2193 [math.CO],

    2014. Available at https://arxiv.org/abs/1410.2193.

[7] P. P. Pach and C. Szabó, On the minimal distance of a polynomial code, Discrete Math. Theor. Comput. Sci. 13 (2011), 33–43.

[8] G. F. Pilz, On polynomial near-ring codes, Contributions to General Algebra 8 (Linz, 1991), 233–238.

[9] N. J. A. Sloane, On the number of ON cells in cellular automata, in Steve Butler et al., eds., Connections in Discrete Mathematics. A Celebration of the Work of Ron Graham, Cambridge University Press, 2018, pp. 13–38. Also available at https://arxiv.org/

    abs/1503.01168.

[10] N. J. A. Sloane et al., On-Line Encyclopedia of Integer Sequences, electronically available

    at https://oeis.org, 2023.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 11Y55. Keywords: symmetric product, symmetric power, binary expansion, odd-rule cellular automaton.

(Concerned with sequences \underline{A000012}, \underline{A001316}, \underline{A048883}, and \underline{A253064}.)

Received June 19 2023; revised versions received June 25 2023; August 1 2023; August 4 2023. Published in Journal of Integer Sequences, August 5 2023.

Return to Journal of Integer Sequences home page.