7
$\begingroup$

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  |
$\endgroup$
11
  • $\begingroup$ 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}$. $\endgroup$ – Michael Wehar Oct 7 '19 at 18:51
  • $\begingroup$ 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/… $\endgroup$ – Michael Wehar Oct 7 '19 at 19:00
  • 1
    $\begingroup$ It would help to post an example of the pairs $(r,d)$ that give the minimal result, e.g. for $n=30$. $\endgroup$ – Matt F. Oct 7 '19 at 21:45
  • 1
    $\begingroup$ Display math $$ $$ works fine in MathJax; there's no need to abuse the formatting to simulate it. $\endgroup$ – LSpice Oct 8 '19 at 1:34
  • 1
    $\begingroup$ @LSpice Thank you! I should have used align for defining the vectors when I originally wrote it. It looks better now! $\endgroup$ – Michael Wehar Oct 8 '19 at 2:12
9
$\begingroup$

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

$\endgroup$
23
  • 2
    $\begingroup$ The asymptotics for the case when $d$ should be prime (or with other restrictions imposed on $d$) might be obtained similarly $\endgroup$ – Ilya Bogdanov Oct 7 '19 at 22:51
  • 1
    $\begingroup$ Great answer. I was thinking along those lines myself. $\endgroup$ – kodlu Oct 8 '19 at 8:19
  • 1
    $\begingroup$ @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)$. $\endgroup$ – mathworker21 Jan 15 '20 at 6:41
  • 1
    $\begingroup$ @MichaelWehar I think his solution is actually simple, but the wording confused me at first and your comments about needing to look up a lot of stuff about linear recurrences made me think the solution actually used a lot of stuff. But I am pretty sure it just uses the thing I mentioned in my previous comment. $\endgroup$ – mathworker21 Jan 15 '20 at 6:42
  • 1
    $\begingroup$ @MichaelWehar well, the definition of characteristic polynomial is based on linear recurrence equations, so I'm not exactly sure what you mean. you should have posted your proof of it here. I'll write down a proof later if you want. Also, I hope you are safe and doing well :) $\endgroup$ – mathworker21 Apr 26 '20 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.