A relationship among multiple periodic arrays

Question

There are N periodic arrays ai[n] with period Ti, respectively, where i=1, 2, … , N. Each array has a property that a[n]=1 when n=k*T where k is integer, otherwise a[n]=0.

Then a new array is created in following format c[n] = a1[n-s1]+a2[n-s2]+…+aN[n-sN], where si is a shift of ai[n].

The question is:

In which situation or by what kind of period set {Ti}, there exists one c[n] so that c[n]<2 (or c[n]=0 or 1) for any n.

For example:

a1[n]={1, 0, 0, 0, 0, 0, 0, 0} with T1=8.

a2[n]={1, 0, 0, 0, 0, 0} with T1=6

a3[n]={1, 0, 0, 0} with T3=4

Above arrays can create required array c[n]:

c[n] = a1[n] + a2[n-1] + a3[n-2] ={1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0} with period 24

But following array cannot do it.

a1[n]={1, 0, 0, 0, 0, 0} with T1=6

a2[n]={1, 0, 0, 0} with T1=4

a3[n]={1, 0, 0} with T3=3

I think there should be a relationship among the input period set {Ti}, such as the largest common divider among {Ti} should be larger than 1.

I’d like to know the intrinsic relationship among the period set {Ti}.

Thanks in advance

Answer 1

Some thoughts on the problem, but no full answer, so posting as CW. Feel free to edit.

1. Note that the array of period $T_i$ has density $(T_i)^{-1}$ in the array c. Therefore by the pigeonhole principle it is necessary that $\sum_{i = 1}^N (T_i)^{-1} \leq 1$.
2. Note that if $T_i$ and $T_j$ are relatively prime, then there exists a solution $(k,l)\in \mathbb{Z}^2$ for the equation $k T_i + l T_j = s$ for any given integer $s$. Therefore necessarily $\mathrm{gcd}(T_i,T_j) > 1$ for any two periods.
3. Note that the above two together is not sufficient: for the set $T_1 = 2$, $T_2 = 4$, $T_3 = 6$ there does not exist any $s_i$ that makes a c that satisfies your condition.
4. So what makes $\{2,4,6\}$ different from $\{4,6,8\}$? In both cases the GCD for the entire set is 2. But we can reduce the first case to the case $\{2,3\}$, using the fact that $s_2-s_1$ and $s_3-s_1$ must both be odd numbers for $\{4,6\}$ not to collide with $\{2\}$.
5. Now, we can re-write your problem as follows. Given a list $\{T_i\}$ of positive integers, you want to find a list $\{s_i\}$ of integers in $[0,\mathrm{lcm}(\{T_i\}))$ such that for every $i,j$ the equation $$ k T_i + s_i = l T_j + s_j $$ has no solution. This shows that $s_i - s_j$ cannot be a multiple of $\mathrm{gcd}(T_i,T_j)$. So equivalently:

   Problem Statement: Given a finite list $\{T_i\}$ of positive integers, is it possible to find a list $\{s_i\} \subset \{0,1,\ldots,\mathrm{lcm}(\{T_i\})\}$ such that for every pair $i,j$, the number $\mathrm{gcd}(T_i,T_j)$ does not divide $s_i - s_j$.

6. This gives us a way to interpret item 4 again. Let $\tau\subset \{T_i\}$ be a subset in which the GCD between any two element is the same number. Hence we have that for $a,b\in \tau$, $\mathrm{gcd}(a,b) = \mathrm{gcd}(\tau)$. By the pigeonhole principle we see that necessarily $\mathrm{gcd}(\tau) \geq |\tau|$. In the case of $\{2,4,6\}$, we can take $\tau$ equal the whole set, which has size 3, but $\mathrm{gcd}(2,4) = \mathrm{gcd}(4,6) = \mathrm{gcd}(2,6) = 2$. In the case of $\{4,6,8\}$ since $\mathrm{gcd}(4,8) = 4$, the pigeonhole principle does not provide an obstacle.