This problem originates from some of my experiments looking at difference of prime numbers, i've removed a lot of the intuition to simplify and shorten the question, if requested I will include it at the end of the question.

Define a signature to be a list of boolean numbers $0,1$. Two signatures $S_1, S_2$ are said to be equal if there exists a signature $S_3$ such that $S_2$ and $S_1$ can be produced by concatenating a natural number of copies $a_2, a_1$ of $S_3$ respectively. Example: $S_1 = [1, 0 ,1], S_2 = [1, 0 ,1 ,1 , 0 , 1]$ then $S_1 = S_2$ since both are a natural number copies of $[1,0,1]$.

Define an elementary signature $S_e$ of a natural number $n \in \mathbb{N}$ as a sequence of binary numbers:

$$[ \underbrace{0, \ 0, \ ... 0}_{n-1 \ \text{times}} \ , 1 ]$$

Example, $S_e(2) = [0, 1]$ $S_e(3) = [0,0,1]$

Define the "overlap" $S_1 \oplus S_2$ of 2 signatures $S_1, S_2$ to be a new signature whose length is the least common multiple of the lengths of $S_1, S_2$ and whose entries are the pairwise boolean OR of each other corresponding elements in $S_1, S_2$.

Example $$S_e(2) \oplus S_e(3) = \\ [0,1] \oplus [0,0,1] =\\ [0, 1, 0, 1, 0, 1] \oplus [0, 0, 1, 0, 0, 1] = [0, 1,1,1, 0 ,1] $$

Now one last definition, we can define the "aggregation" $\aleph(S)$ of a signature $S$, to be a list of natural numbers, where for every sequence of non-zero values in the signature the aggregation carries a single element equal to their sum.


$$\aleph(S_e(5)) = \aleph([0,0,0,0,1]) = [0,0,0,0,1]$$ $$\aleph(S_e(2) \oplus S_e(3) ) = \aleph([0,1,1,1,0,1]) = [0, 1+1+1, 0, 1] = [0,3,0,1]$$ $$\aleph(S_e(2) \oplus S_e(3) \oplus(S_e(5)) =\\ \aleph([0,1,1,1,0,1] \oplus [0,0,0,0,1]) = \\ \aleph([0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,...]) = \\ [0,1+1+1+1+1, 0, 1+1+1, 0 ,1 ...] = \\ [0,5,0,3,0,1,0,3,0, 1,0,3,0,5,0,1] $$

If you look at the lengths of the signatures denoted by $\dim$ (to be formal the length is the length of smallest member of the equivalence class given by a signature)

$$ \dim \aleph(S_e(2)) = 2 $$ $$ \dim \aleph(S_e(2) \oplus S_e(3)) = 4$$ $$ \dim \aleph(S_e(2) \oplus S_e(3) \oplus S_e(5)) = 16 $$ $$ \dim \aleph(S_e(2) \oplus S_e(3) \oplus S_e(5) \oplus S_e(7)) = 96 $$ $$ \dim \aleph(S_e(2) \oplus S_e(3) \oplus S_e(5) \oplus S_e(7) \oplus S_e(11) ) = 960 $$

Notice $$4 = (3-1)(2) \\ 16 = (5-1)(4) \\ 96 = (7-1)(16) \\ 960 = (11 - 1)(96) \\ \vdots $$

This leads to the natural conjecture, which I'm trying to prove (let $P_n$ denote the $n^{\text{th}}$ prime number)

$$ \dim \aleph \left( \bigoplus_{i=1}^{n} S_e(P_i) \right) = 2\prod_{i=1}^{n} (P_i - 1) $$

What subject does this fall under? What type of machinery would be needed to do this.

  • 1
    $\begingroup$ You might want to define two signatures "equaling" each other slightly differently so that $A=B\iff B=A:$ elsewise, you end up with $=$ denoting a relation that is not an equivalence relation, and doesn't act how $=$ is generally assumed to act. $\endgroup$ – Austin Weaver Oct 20 '17 at 18:16
  • 2
    $\begingroup$ It doesn't seem coincidental that $\phi(\#_n)=\prod_{i=1}^n(P_i-1)$, where $\#_n$ is the primorial product. So likely this is calculating the order of the group $\mathbb{Z}\backslash \mathbb{Z}_{\#_n}$ in a different way, and in fact in this case by the chinese remainder thoerem: $\mathbb{Z}\backslash \mathbb{Z}_{\#_n}=\mathbb{Z}\backslash \mathbb{Z}_{P_1}\times\cdots\times \mathbb{Z}\backslash \mathbb{Z}_{P_n}$ $\endgroup$ – Alex R. Oct 20 '17 at 18:51
  • 1
    $\begingroup$ @AustinWeaver noted! I modified the definition to adjust for that $\endgroup$ – frogeyedpeas Oct 20 '17 at 19:08

First, I will show that $\dim\aleph\left(\bigoplus_{i=1}^nS_e(p_i)\right)$ is equal to twice the number of $0$'s in $\bigoplus_{i=1}^nS_e(p_i)$. Now, this immediately follows from the fact that there are no adjacent $0$'s in the overlap, and the fact that the overlap starts with $0$ and ends in $1$. But how do we know there are no adjacent $0$'s in the overlap? Because every other item of the overlap is guaranteed to be $1$, coming from the $S_e(2)$.

We have established that the LHS of your conjecture is equal to twice the number of $0$'s in the overlap. So now all we have to show is that the number of $0$'s in the overlap is equal to $\prod_{i=1}^n(p_i-1).$ This product is also equal to $\varphi\left(\prod_{i=1}^np_i\right)$ where $\varphi$ is Euler's totient function. See here.

Let's think about what it means for the $k$th entry of the overlap to be a $0$. For this to be true, the $k$th entry of each $S_e(p_1),S_e(p_2),\dots,S_e(p_n)$ must be $0$. In other words, $k$ must be coprime to each $p_1,p_2,\dots,p_n$. This is equivalent to saying $k$ must be coprime to $\prod_{i=1}^np_i$. The number of all such $k< \prod_{i=1}^np_i$ is exactly $\varphi\left(\prod_{i=1}^np_i\right)$ by definition.

Therefore, we have shown that $$\dim\aleph\left(\bigoplus_{i=1}^nS_e(p_i)\right)=2\prod_{i=1}^n(p_i-1)$$


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.