**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  |

```


Do the following binary vectors span $\mathbb{R}^n$?
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}$.


