# Binary vectors defined by remainders modulo prime numbers. What is the dimension of their span?

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)

• Have you computed any small examples, to get a feel for what's going on? Commented Sep 18, 2019 at 4:44
• @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. Commented Sep 18, 2019 at 4:50
• 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! Commented Sep 18, 2019 at 5:34
• It's not nice to change the question after someone has posted an answer. Commented Sep 18, 2019 at 5:50
• @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. Commented Sep 19, 2019 at 21:58

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.

• This is a good point! Further, any idea on what bounds can be given for $dim(V)$? Commented Sep 18, 2019 at 4:55

Suppose $$\dim(V) < n$$. Then there is some nonzero vector $$x$$ orthogonal to all the $$v_{r,p}$$'s, which it's easy to see implies $$\sum_{j=1}^n x_j z^j$$ has roots at $$z = e^{2\pi i \frac{m}{p}}$$ for each $$p \le k$$ and $$0 \le m \le p-1$$, so since $$x$$ is nonzero and $$\sum_{j=1}^n x_jz^j$$ is a degree $$n$$ polynomial, we must have $$1+\sum_{p \le k} (p-1) \le n$$.

• If I understand correctly, then by contrapositive we have the following. If $\sum_{p \le k} (p-1) \geq n$, then $dim(V) = n$. Also, just to be clear, the sum is only over primes $p$ less than or equal to $k$. Commented Apr 26, 2020 at 1:03
• @MichaelWehar In response to your first comment, yup! In response to your second comment, separate the sum based on the residue of $j$ mod $p$: $\sum_{j=1}^n x_je(\frac{mj}{p}) = \sum_{i=0}^{p-1} e(\frac{mi}{p})\sum_{j=1 \\ j \equiv i \text{ mod p}}^n x_j = \sum_{i=0}^{p-1} e(\frac{mi}{p}) (x\cdot v_{i,p})$ Commented Apr 26, 2020 at 5:15
• @MichaelWehar thanks :) what else needs explanation? and yea Commented Apr 27, 2020 at 10:29
• I could be mistaken, but I think it should be $\sum_{j=1}^n x_jz^j$ has degree $d \leq n$, we must have $1+\sum_{p \le k} (p-1) \le d$. Therefore, $1+\sum_{p \le k} (p-1) \le n$. Commented Apr 27, 2020 at 10:37
• @MichaelWehar ok, sure Commented Apr 27, 2020 at 10:48

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.

• 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. :) Commented Sep 22, 2019 at 9:10
• @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. Commented Sep 22, 2019 at 21:32
• @MichaelWehar thanks! ill still think about it. feel free to ping me in the comments here in a few months Commented Sep 26, 2019 at 9:39
• @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? Commented Oct 8, 2019 at 14:58
• @MichaelWehar wait, Ilya says the answer is $\sqrt{n}$, but my answer shows the (trivial) lower bound of $\sqrt{n\log n}$. Commented Oct 8, 2019 at 15:00

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!

• Note that $\deg\Phi_p=p-1$. Not that it matters much... Commented Oct 9, 2019 at 4:59
• @MichaelWehar Hi. I'm just getting to this now. I don't understand Ilya's solution on MO. First of all, what does he/she mean by "linear recurrence"? Commented Nov 3, 2019 at 23:32
• @MichaelWehar Thanks for your response! Do you want to just post a complete answer here (on your answer)? It will (1) be a good review for you and (2) save me and others much time Commented Nov 4, 2019 at 0:31
• @mathworker21 Yes, I would like to do this, but first I need to find better sources on linear recurrences and cyclotomic polynomials so that I have something I can reference. Commented Nov 4, 2019 at 0:42
• @MichaelWehar I'd be very appreciative, as this is an interesting solution. Commented Nov 4, 2019 at 0:44