# Do the following binary vectors span $\mathbb{R}^n$?

Defining the binary vectors

Let an ordered triple of natural numbers $$(r, d, n)$$ such that $$0 \leq r < d \leq n$$ be given.

Consider the binary vector $$v_{(r,d,n)} \in \mathbb{R}^n$$ such that for all $$i \in \{0\} \cup [n-1]$$: \begin{align*} (v_{(r,d,n)})_i = 1 & \quad\text{if i \equiv r \mod d} \\ (v_{(r,d,n)})_i = 0 & \quad\text{otherwise.} \end{align*}

In other words, $$r$$ is the remainder, $$d$$ is the divisor, and $$n$$ is the dimension.

An example vector

Let's take $$r = 1$$, $$d = 3$$, and $$n = 14$$. In this case, we have:

$$v_{(1,3,14)} = (0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1).$$

Defining the subspaces

Let an ordered pair of natural numbers $$(m, n)$$ such that $$m \leq n$$ be given.

Consider the subspace $$V_{(m,n)} \subseteq \mathbb{R}^n$$ given by $$V_{(m,n)} = \operatorname{span} \{ v_{(r, d, n)} \; \vert \; 0 \leq r < d \leq m \}.$$ In other words, $$m$$ is a bound for the divisor.

My Question

Let a natural number $$n$$ be given.

Consider the function $$k(n)$$ given by: $$k(n) \mathrel{:=} \min \{ m \; \vert \; V_{(m,n)} = \mathbb{R}^n \}.$$

Without much effort, it can be shown that $$k(n) \leq n$$ and $$k(n) = \Omega(\sqrt{n})$$.

Can we prove asymptotically tighter bounds on $$k(n)$$? My intuition is that $$k(n) = O(\sqrt{n} \cdot \log(n))$$.

Update 1

The problem has be solved thanks to @Ilya Bogdanov.

Below I added a snippet of Octave code in case anyone is interested in checking on smaller values of $$n$$.

As requested, for the $$n = 30$$ case, we have $$k(30) = 10$$.

% Parameters
n = 30
m = 10

% Compute number of rows & cols
rows = (m + 1) * m / 2
cols = n

% Construct matrix
M = zeros(rows, cols);
count = 1;
for d = 1:m
for r = 0:(d-1)
for c = 1:cols
if r == mod(c-1, d)
M(count, c) = 1;
end
end
count += 1;
end
end

% Print matrix
M

% Print rank
rankOfM = rank(M)


Update 2

Below is a table of values for $$k(n)$$ when $$1 \leq n \leq 50$$.

| n  | k(n) |
-------------
| 1  |  1   |
| 2  |  2   |
| 3  |  3   |
| 4  |  3   |
| 5  |  4   |
| 6  |  4   |
| 7  |  5   |
| 8  |  5   |
| 9  |  5   |
| 10 |  5   |
| 11 |  6   |
| 12 |  6   |
| 13 |  7   |
| 14 |  7   |
| 15 |  7   |
| 16 |  7   |
| 17 |  7   |
| 18 |  7   |
| 19 |  8   |
| 20 |  8   |
| 21 |  8   |
| 22 |  8   |
| 23 |  9   |
| 24 |  9   |
| 25 |  9   |
| 26 |  9   |
| 27 |  9   |
| 28 |  9   |
| 29 |  10  |
| 30 |  10  |
| 31 |  10  |
| 32 |  10  |
| 33 |  11  |
| 34 |  11  |
| 35 |  11  |
| 36 |  11  |
| 37 |  11  |
| 38 |  11  |
| 39 |  11  |
| 40 |  11  |
| 41 |  11  |
| 42 |  11  |
| 43 |  12  |
| 44 |  12  |
| 45 |  12  |
| 46 |  12  |
| 47 |  13  |
| 48 |  13  |
| 49 |  13  |
| 50 |  13  |

• I did write some code in Octave to try out some smaller cases when $n < 500$. The experiment seemed to be inconclusive. But, I still think it should be close to $\sqrt{n}$. – Michael Wehar Oct 7 '19 at 18:51
• I did a related post a couple weeks ago and @mathworker21's answer and discussion led me to the current question. The old post asked some questions related to when the divisor is a prime number and we obtained some small results: math.stackexchange.com/questions/3360599/… – Michael Wehar Oct 7 '19 at 19:00
• It would help to post an example of the pairs $(r,d)$ that give the minimal result, e.g. for $n=30$. – Matt F. Oct 7 '19 at 21:45
• Display math  works fine in MathJax; there's no need to abuse the formatting to simulate it. – LSpice Oct 8 '19 at 1:34
• @LSpice Thank you! I should have used align for defining the vectors when I originally wrote it. It looks better now! – Michael Wehar Oct 8 '19 at 2:12

Let $$v_{r,d}$$ be an infinite sequence defined in the same way, and let $$V_m$$ be the span of all corresponding sequences with $$d\leq m$$.
For a fixed $$d$$, the linear span of all $$v_{r,d}$$ is the set of all linear recurrences with characteristic polynomial $$x^d-1=\prod_{k\mid d} \Phi_k(x),$$ where $$\Phi_k$$ is the $$k$$th cyclotomic polynomial. Therefore, $$V_{m}$$ is the set of all linear recurrences with characteristic polynomial $$P_m(x)= \mathop{\mathrm{lcm}}\left\{x^d-1\colon d\leq m\right\}= \prod_{k\leq m} \Phi_k(x).$$ Thus, whenever $$\deg P_m\geq n$$, the sequences from $$V_m$$ may have arbitrary first $$n$$ terms, so $$V_{m,n}=\mathbb R^n$$. Conversely, if $$\deg P_m, the set $$V_{m,n}$$ is not the whole space due to dimension reasons.
The inequality rewrites as $$S_m= \sum_{k\leq m}\varphi(k)\geq n.$$ The asymptotics of $$S_m$$ is known (see, e.g., https://en.wikipedia.org/wiki/Farey_sequence) and is $$S_m\sim3m^2/\pi^2$$ (this can be easily derived from the number of coprime pairs of positive integers not exceeding $$m$$). Hence, the correct order is indeed $$k(n)\sim \pi \sqrt{n/3}$$.
• The asymptotics for the case when $d$ should be prime (or with other restrictions imposed on $d$) might be obtained similarly – Ilya Bogdanov Oct 7 '19 at 22:51
• @MichaelWehar idk why you're defining "linear recurrence" differently from Ilya. It's very clear that Ilya defined it as just an infinite sequence; I think things will be easier if you stuck with his definition. Instead of your comment talking about solution sets: He is just using the fact that the span of the set of all linear recurrences with characteristic polynomial $P_1$ and the set of all linear recurrences with characteristic polynomial $P_2$ is the set of all linear recurrences with characteristic polynomial $lcm(P_1,P_2)$. – mathworker21 Jan 15 '20 at 6:41