Let $G$ be a finite group, $S \subset G$ a generating set, $|g|:=|g|_S=$ word-length with respect to $S$. Let $\phi(g,h)=|g|+|h|-|gh| \ge 0$ be the "defect-function" of $S$. The set $\mathbb{Z}\times G$ builds a group for the following operation:

$$(a,g) \oplus (b,h) = (a+b+\phi(g,h),gh)$$

On $\mathbb{N}\times G$ is the "norm": $|(a,g)| := |a|+|g|$ additive, which means that $|a \oplus b| = |a|+|b|$. Define the multiplication with $n \in \mathbb{N_0}$ to be:

$$ n \cdot a := a \oplus a \oplus \cdots \oplus a$$

(if $n=0$ then $n \cdot a := (0,1) \in \mathbb{Z} \times G$).

A word $w := w_{n-1} w_{n-2} \cdots w_0$ is mapped to an element of $\mathbb{Z} \times G$ as follows:

$$\zeta(w) := \oplus_{i=0}^{n-1} (m^i \cdot (0,w_i))$$

where $m := \min_{g,h\in G, \phi(g,h) \neq 0} \phi(g,h)$.

We let $|w|:=|\zeta(w)|$ and $w_1 \oplus w_2:=\zeta(w_1)\oplus \zeta(w_2)$

Then we have $|w_1 \oplus w_2| = |w_1|+|w_2|$.

For instance for the Klein four group $\{0,a,b,c=a+b\}$ generated by $S:=\{a,b\}$, we get sorting the words $w$ by their word-length:


corresponding to the following $\mathbb{Z}\times K_4$ elements $\zeta(w)$:


corresponding to the the following "norms" of words $|w| = |\zeta(w)|$:


Let $a_n, n\ge 0$ be the sequence of numbers generated by the Klein four group.

1) Is $$\sum_{n=1}^\infty \frac{1}{a_n^s} = \sum_{n=1}^\infty \frac{n+1}{n^s} = \zeta(s-1) + \zeta(s)$$ where $\zeta$ denotes the Riemann zeta function?

I have checked this with SAGE math up to a certain degree and it seems plausible, however I have no idea how to prove it.

2) Is every $a_n$ the product of primes $p=a_k$ for some $k\le n$?

3) Let $\pi_{K_4}(n) = |\{ k : \text{$a_k$ is prime, $k \le n$}\}|$ be the prime counting function of the sequence. What is the approximate relationship to the usual prime counting function $\pi(n)$?

  • $\begingroup$ What is your definition of $a_n$? $\endgroup$ – Thomas Browning Jan 28 at 3:39
  • $\begingroup$ @ThomasBrowning It is the sequence for the Klein group defined in the previous question. $\endgroup$ – user6671 Jan 28 at 3:49
  • $\begingroup$ I don't see an integer sequence defined in the previous question $\endgroup$ – Thomas Browning Jan 28 at 3:53
  • $\begingroup$ @ThomasBrowning mathoverflow.net/a/351113/6671 sorry it was defned in the answer $\endgroup$ – user6671 Jan 28 at 3:54
  • $\begingroup$ Are you talking about this sequence: 0,1,1,2,2,3,3,4,2,3,3,4,4,5,5,6,4,5,5,6? This sequence seems to depend upon a lexicographic ordering of words. Is this correct? $\endgroup$ – Thomas Browning Jan 28 at 4:02

Consider a word $w=w_0w_1\cdots w_{n-1}$ with each $w_i\in\{0,a,b,c\}$. Following your notation, $$\lvert w\rvert=\lvert\zeta(w)\rvert=\left\lvert\bigoplus_{i=0}^\infty m^i\cdot(0,w_i)\right\rvert=\sum_{i=0}^{n-1}\lvert 2^i\cdot(0,w_i)\rvert=\sum_{i=0}^{n-1} 2^i\lvert w_i\rvert$$ where $\lvert0\rvert=0$, $\lvert a\rvert=1$, $\lvert b\rvert=1$, $\lvert c\rvert=2$. We now consider the generating function $$F_n(x)=\sum_wx^{\lvert w\rvert}$$ where the sum is over all words $w=w_0w_1\cdots w_{n-1}$. Then \begin{align*} F_n(x)&=\sum_{w_0}\sum_{w_1}\cdots\sum_{w_{n-1}}x^{|w_0|+2|w_1|+\cdots+2^{n-1}|w_{n-1}|}\\ &=\left(\sum_{w_0}x^{|w_0|}\right)\left(\sum_{w_1}x^{2|w_1|}\right)\cdots\left(\sum_{w_{n-1}}x^{2^{n-1}|w_{n-1}|}\right)\\ &=(1+2x+x^2)(1+2x^2+x^4)(1+2x^4+x^8)\cdots(1+2x^{2^{n-1}}+x^{2^n})\\ &=(1+x)^2(1+x^2)^2(1+x^4)^2\cdots(1+x^{2^{n-1}})^2\\ &=(1+x+x^2+\cdots+x^{2^n-1})^2\\ &=1+2x+\cdots+(2^n-1)x^{2^n-2}+2^nx^{2^n-1}+(2^n-1)x^{2^n}+\cdots+x^{2^{n+1}-2}. \end{align*}

What this shows is that among the first $4^n$ terms of the sequence: \begin{align*} &0\text{ appears }1\text{ times},\\ &1\text{ appears }2\text{ times},\\ &2\text{ appears }3\text{ times},\\ &\cdots\\ &2^n-2\text{ appears }2^n-1\text{ times},\\ &2^n-1\text{ appears }2^n\text{ times},\\ &2^n\text{ appears }2^n-1\text{ times},\\ &\cdots\\ &2^{n+1}-4\text{ appears }3\text{ times},\\ &2^{n+1}-3\text{ appears }2\text{ times},\\ &2^{n+1}-2\text{ appears }1\text{ times}.\\ \end{align*} This resolves question 1. Since this seems to be purely a combinatorics question, I would not expect the second and third questions to have particularly interesting answers.

I will remark that $$\pi_{K_4}(4^n)=\sum_{p\leq2^{n+1}-2}(2^n-\lvert p-2^n+1\rvert)p$$ so you could use some analytic number theory to get asymptotics for $\pi_{K_4}(n)$ if you wanted.

| cite | improve this answer | |
  • $\begingroup$ thanks for your answer. very interesting $\endgroup$ – user6671 Jan 28 at 5:50

Your Answer

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