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

Question

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  |

Answer 1

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<n$, 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}$.