Vectores binarios definidos por los restos de los números primos. ¿Cuál es la dimensión de su tramo?

Question

Que los números $n$ y $k$ tal que $k \leq n$ se le dará.

Dejemos que $S$ sea el conjunto de números primos menores o iguales a $k$ .

Definimos un vector binario $v_{p, r}$ de longitud $n$ para cada $p \in S$ y $r \in [p - 1] \cup \{0\}$ de la siguiente manera.

Para cada $i \in [n-1] \cup \{0\}$ :

• $(v_{p, r})_i = 1$ si $i \equiv r \; mod \; p$
• $(v_{p, r})_i = 0$ De lo contrario,

Consideremos el conjunto de todos esos vectores binarios $X := \{ \; v_{p, r} \; | \; p \in S \text{ and } r \in [p - 1] \cup \{0\} \; \}$ .

Pregunta 1: Es $X$ linealmente independiente sobre $\mathbb{R}^{n}$ ? (No. Ver respuesta de @ChrisCulter)

Además, consideremos el espacio vectorial $V := span(X)$ tal que $V$ se ve como un subespacio de $\mathbb{R}^{n}$ .

Estoy tratando de encontrar límites en $dim(V)$ en términos de $n$ y $k$ . Cualquier respuesta sería muy apreciada, pero específicamente estoy tratando de responder a lo siguiente.

Pregunta 2: ¿Cuál es el menor $k$ (en términos de $n$ ) tal que $dim(V) = n$ ? ¿Podemos elegir siempre $k$ lo suficientemente grande como para garantizar que $dim(V) = n$ ?

---

Actualización

Basándome en la sugerencia de @GerryMyerson, he codificado algunos ejemplos en Octave.

Cuando $n = 400$ y $k = 61$ tenemos $dim(V) = n = 400$ .

Esto sugiere que podríamos encontrar un límite superior para el menor $k$ (en relación con $n$ ) tal que $dim(V) = n$ .

Aquí está mi código de Octave por si alguien quiere probarlo:

% 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)

Answer 1

No, si $k>3$ entonces $V$ no es linealmente independiente (sobre cualquier campo). Podemos escribir el todo- $1$ s como dos combinaciones lineales diferentes: $$\sum_r v_{2,r} = \sum_r v_{3,r}.$$ Lo mismo ocurre si $X$ es cualquier conjunto que contenga al menos dos números.

Answer 2

Para $n \ge 1$ , dejemos que $k(n)$ denotan el valor mínimo de $k$ para los que el $V$ tiene $\dim(V) = n$ .

Reclamación: Por cada $\epsilon > 0$ , $k(n) \ge (1-\epsilon)\sqrt{n\log n}$ para todos los grandes $n$ .

Prueba: Menos de $n$ Los vectores no pueden abarcar un $n$ -espacio dimensional, por lo que debemos tener $n \le \sum_{p \le k} p \sim \frac{1}{2}\frac{k^2}{\log k}$ . Claramente $k \le \sqrt{n}$ implica $\frac{1}{2}\frac{k^2}{\log k} \le n$ . Y si $k \in [\sqrt{n},(1-\epsilon)\sqrt{n\log n}]$ entonces $\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$

.

Reclamación: Por cada $\epsilon > 0$ , $k(n) \le (\frac{3}{4}+\epsilon)n$ para todos los grandes $n$ . En particular, la respuesta a la segunda mitad de la pregunta 2 es "sí".

Prueba: Por pura pereza, voy a probar $k(n) \le \frac{9n}{10}$ para todos los grandes $n$ . La cantidad de esfuerzo para adaptar lo siguiente a $(\frac{3}{4}+\epsilon)n$ es menor que para escribir esta frase actual. Por el teorema de los números primos, podemos tomar algún primo $p \in (\frac{9n}{10},n)$ . Entonces, para $\frac{n}{10} \le r \le p-1$ , $v_{p,r} = e_r$ (donde $e_j = (0,\dots,0,1,0,\dots,0)$ El $1$ en el índice $j$ ). Tome un poco de $q \in (\frac{n}{2},\frac{8n}{10})$ . Entonces, para $0 \le r \le \frac{n}{10}$ , $v_{q,r} = e_r+e_{q+r}$ Así que $v_{q,r}+v_{p,q+r} = e_r$ (nota $q+r < p$ Así que $v_{p,q+r}$ es válido). Por último, para $p \le r \le n-1$ , $v_{q,r-q} = e_{r-q}+e_r$ Así que $v_{q,r-q}+v_{p,r-q} = e_r$ . $\square$

.

Ahora algunos resultados y especulaciones menores.

Dejemos que $v_1 = (1,1,1,\dots,1)$ y $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$ .

Conjetura: Para $n \ge 4$ , $v_1,\dots,v_n$ son linealmente independientes en $\mathbb{R}^n$ .

Esta es la conjetura natural a la luz de la dependencia obvia señalada por Chris Cutler ( $n=2,3$ son demasiado pequeños por razones tontas).

Por desgracia, esta conjetura es falsa, y $n=11$ es el contraejemplo más pequeño. Sin embargo, a partir del código parece que es casi cierto. Si la conjetura fuera cierta, entonces el valor mínimo de $k$ para lo cual $\dim(V) = n$ es el valor mínimo de $k$ para lo cual $1+ \sum_{p \le k} (p-1) \ge n$ . Mediante la suma parcial y el teorema de los números primos, se puede ver que $\sum_{p \le k} p \sim \frac{1}{2}\frac{k^2}{\log k}$ Así que la respuesta sería básicamente $k = \sqrt{n\log n}$ . Dado que la conjetura parece ser casi cierta, supongo que $k = \Theta(\sqrt{n\log n})$ es la respuesta a la pregunta 2.

Answer 3

Supongamos que $\dim(V) < n$ . Entonces hay algún vector no nulo $x$ ortogonal a todos los $v_{r,p}$ 's, lo que es fácil de ver implica $\sum_{j=1}^n x_j z^j$ tiene sus raíces en $z = e^{2\pi i \frac{m}{p}}$ para cada $p \le k$ y $0 \le m \le p-1$ Así que, como $x$ es distinto de cero y $\sum_{j=1}^n x_jz^j$ es un grado $n$ polinomio, debemos tener $1+\sum_{p \le k} (p-1) \le n$ .

Answer 4

Podemos utilizar el mismo enfoque que presentó @Ilya Bogdanov aquí: https://mathoverflow.net/questions/343355/do-the-following-binary-vectors-span-mathbbrn

Siguiendo el mismo formato, obtenemos un polinomio $$P_k(x) = \prod_{\substack{ p \, \in \, \mathtt{PRIMES \hspace{0.08em} \cup \hspace{0.08em} \{1\}}\\ p \leq k }} \Phi_p(x).$$

Por lo tanto, el grado de $P_k$ es igual a $$1 + \sum_{\substack{ p \, \in \, \mathtt{PRIMES}\\ p \leq k }} (p - 1).$$

Además, obtenemos que el grado de $P_k \sim \frac{k^2}{2 \log k}$ aplicando los resultados de: Cuál es la suma de los números primos hasta un número primo $n$ ?

Tenemos que $dim(V) = n$ precisamente cuando el grado de $P_k \geq n$ .

Por lo tanto, $k(n) = \Theta(\sqrt{n \log n})$ como conjetura @mathworker21.

¡Muchas gracias @Ilya Bogdanov y @mathworker21!