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

`$$ $$`

works fine in MathJax; there's no need to abuse the formatting to simulate it. $\endgroup$ – LSpice Oct 8 '19 at 1:346more comments