1
$\begingroup$

Let numbers $n$ and $k$ such that $k \leq n$ be given.

Let $S$ be the set of prime numbers less than or equal to $k$.

We define a binary vector $v_{p, r}$ of length $n$ for each $p \in S$ and $r \in [p - 1] \cup \{0\}$ as follows.

For each $i \in [n-1] \cup \{0\}$:

  • $(v_{p, r})_i = 1$ if $i \equiv r \; mod \; p$
  • $(v_{p, r})_i = 0$ otherwise

Consider the set of all such binary vectors $X := \{ \; v_{p, r} \; | \; p \in S \text{ and } r \in [p - 1] \cup \{0\} \; \}$.

Question 1: Is $X$ linearly independent over $\mathbb{R}^{n}$? (No. See answer by @ChrisCulter)

Further, consider the vector space $V := span(X)$ such that $V$ is viewed as a subspace of $\mathbb{R}^{n}$.

I am trying to find bounds on $dim(V)$ in terms of $n$ and $k$. Any bounds would be greatly appreciated, but I am specifically trying to answer the following.

Question 2: What is the smallest $k$ (in terms of $n$) such that $dim(V) = n$? Can we always pick $k$ large enough to guarantee that $dim(V) = n$?


Update

Based on @GerryMyerson's suggestion, I coded up some examples in Octave.

When $n = 400$ and $k = 61$, we have $dim(V) = n = 400$.

This suggests that we might be able to find an upper bound on the smallest $k$ (relative to $n$) such that $dim(V) = n$.

Here is my Octave code in case anyone wants to give it a try:

% Parameters
n = 400
k = 61

% Prime numbers
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113];
primes = primes(find(primes <= k));

% Compute number of rows & cols
count = 0;
for p = primes
  count += p;
end
rows = count
cols = n

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

% Print rank
rankOfM = rank(M)
$\endgroup$
  • 4
    $\begingroup$ Have you computed any small examples, to get a feel for what's going on? $\endgroup$ – Gerry Myerson Sep 18 at 4:44
  • $\begingroup$ @GerryMyerson This is a great suggestion! I tried to do it by hand, but the examples are fairly large. Maybe I could code something up in MATLAB. $\endgroup$ – Michael Wehar Sep 18 at 4:50
  • $\begingroup$ Note: The question was modified several times until it got to its current form which most accurately captures what I'm looking for. Thank you! $\endgroup$ – Michael Wehar Sep 18 at 5:34
  • 3
    $\begingroup$ It's not nice to change the question after someone has posted an answer. $\endgroup$ – Gerry Myerson Sep 18 at 5:50
  • $\begingroup$ @GerryMyerson Thank you for the comment! My original post had some issues. I thought it was best to improve it, but it might have been better if I had posted a new question. The answer that was posted is valuable and still relevant. $\endgroup$ – Michael Wehar Sep 19 at 21:58
4
$\begingroup$

No, if $k>3$ then $V$ is not linearly independent (over any field). We can write the all-$1$s vector as two different linear combinations: $$\sum_r v_{2,r} = \sum_r v_{3,r}.$$ The same occurs if $X$ is any set containing at least two numbers.

$\endgroup$
  • $\begingroup$ This is a good point! Further, any idea on what bounds can be given for $dim(V)$? $\endgroup$ – Michael Wehar Sep 18 at 4:55
1
+50
$\begingroup$

For $n \ge 1$, let $k(n)$ denote the minimum value of $k$ for which the associated $V$ has $\dim(V) = n$.

Claim: For each $\epsilon > 0$, $k(n) \ge (1-\epsilon)\sqrt{n\log n}$ for all large $n$.

Proof: Less than $n$ vectors can't span an $n$-dimensional space, so we must have $n \le \sum_{p \le k} p \sim \frac{1}{2}\frac{k^2}{\log k}$. Clearly $k \le \sqrt{n}$ implies $\frac{1}{2}\frac{k^2}{\log k} \le n$. And if $k \in [\sqrt{n},(1-\epsilon)\sqrt{n\log n}]$, then $\frac{1}{2}\frac{k^2}{\log k} \le \frac{1}{2}\frac{(1-\epsilon)n\log n}{\log\sqrt{n}} = (1-\epsilon)n$. $\square$

.

Claim: For each $\epsilon > 0$, $k(n) \le (\frac{3}{4}+\epsilon)n$ for all large $n$. In particular, the answer to the second half of question 2 is "yes".

Proof: Out of pure laziness, I'll just prove $k(n) \le \frac{9n}{10}$ for all large $n$. The amount of effort to adapt the following to $(\frac{3}{4}+\epsilon)n$ is less than that to write this current sentence. By the prime number theorem, we may take some prime $p \in (\frac{9n}{10},n)$. Then, for $\frac{n}{10} \le r \le p-1$, $v_{p,r} = e_r$ (where $e_j = (0,\dots,0,1,0,\dots,0)$, the $1$ in index $j$). Take some $q \in (\frac{n}{2},\frac{8n}{10})$. Then, for $0 \le r \le \frac{n}{10}$, $v_{q,r} = e_r+e_{q+r}$, so $v_{q,r}+v_{p,q+r} = e_r$ (note $q+r < p$, so $v_{p,q+r}$ is valid). Finally, for $p \le r \le n-1$, $v_{q,r-q} = e_{r-q}+e_r$, so $v_{q,r-q}+v_{p,r-q} = e_r$. $\square$

.

Now some minor results and speculations.

Let $v_1 = (1,1,1,\dots,1)$ and $v_2,v_3,v_4,\dots = v_{2,1},v_{3,1},v_{3,2},v_{5,1},v_{5,2},v_{5,3},v_{5,4},v_{7,1}\dots,v_{7,6},v_{11,1}\dots$.

Conjecture: For $n \ge 4$, $v_1,\dots,v_n$ are linearly independent in $\mathbb{R}^n$.

This is the natural conjecture to make in light of the obvious dependence pointed out by Chris Cutler ($n=2,3$ are too small for silly reasons).

Unfortunately, this conjecture is false, and $n=11$ is the smallest counter-example. However, it appears from code to be nearly true. If the conjecture were true, then the minimum value of $k$ for which $\dim(V) = n$ is the minimum value of $k$ for which $1+ \sum_{p \le k} (p-1) \ge n$. By partial summation and the prime number theorem, one can see that $\sum_{p \le k} p \sim \frac{1}{2}\frac{k^2}{\log k}$, so the answer would be basically $k = \sqrt{n\log n}$. Since the conjecture seems to be nearly true, I would guess $k = \Theta(\sqrt{n\log n})$ is the answer to question 2.

$\endgroup$
  • 1
    $\begingroup$ Thank you so much! I really liked how you laid everything out. Reading your answer, makes me feel like I better understand the problem. Also, I liked how you removed the remainder 0 case and I feel it's surprising how your conjecture fails, but it seems to be nearly correct. I feel like we should be able to prove your suggested upper bound and I am hopeful that we can. :) $\endgroup$ – Michael Wehar Sep 22 at 9:10
  • 1
    $\begingroup$ @MichaelWehar very nice question! still trying to get anything $o(n)$ for an upper bound. see my updated answer. I'm feeling kind of sluggish for not getting a better upper bound. My mind just gets confused thinking about too many vectors. Let me know if you figure out anything. $\endgroup$ – mathworker21 Sep 22 at 21:32
  • 1
    $\begingroup$ @MichaelWehar thanks! ill still think about it. feel free to ping me in the comments here in a few months $\endgroup$ – mathworker21 Sep 26 at 9:39
  • 1
    $\begingroup$ @MichaelWehar thanks for telling me! I have to run right now, but it seems that Ilya's answer is seeming to say that the false conjecture in my answer is true. Am I mistaken? $\endgroup$ – mathworker21 Oct 8 at 14:58
  • 1
    $\begingroup$ @MichaelWehar wait, Ilya says the answer is $\sqrt{n}$, but my answer shows the (trivial) lower bound of $\sqrt{n\log n}$. $\endgroup$ – mathworker21 Oct 8 at 15:00
0
$\begingroup$

We can use the same approach as was presented by @Ilya Bogdanov here: https://mathoverflow.net/questions/343355/do-the-following-binary-vectors-span-mathbbrn

Following the same format, we get a polynomial $$P_k(x) = \prod_{\substack{ p \, \in \, \mathtt{PRIMES \hspace{0.08em} \cup \hspace{0.08em} \{1\}}\\ p \leq k }} \Phi_p(x).$$

Therefore, the degree of $P_k$ is equal to $$1 + \sum_{\substack{ p \, \in \, \mathtt{PRIMES}\\ p \leq k }} (p - 1).$$

Further, we get that the degree of $P_k \sim \frac{k^2}{2 \log k}$ by applying results from: What is the sum of the prime numbers up to a prime number $n$?

We have that $dim(V) = n$ precisely when degree of $P_k \geq n$.

Therefore, $k(n) = \Theta(\sqrt{n \log n})$ as conjectured by @mathworker21.

Thank you very much @Ilya Bogdanov and @mathworker21!

$\endgroup$
  • 1
    $\begingroup$ Note that $\deg\Phi_p=p-1$. Not that it matters much... $\endgroup$ – Ilya Bogdanov Oct 9 at 4:59
  • $\begingroup$ @IlyaBogdanov Great catch! You're totally right. I will fix it now. Thank you. :) $\endgroup$ – Michael Wehar Oct 9 at 7:06

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.