El diámetro más pequeño de un subconjunto equilibrado del cubo Hamming

Question

Deje que $\{0,1\}^n$ ser el cubo de Hamming con el La métrica de Hamming . Es un espacio métrico de diámetro $n$ . Llamemos a un grupo $B \subset \{0,1\}^n$ equilibrado si su centro de masa es el centro del cubo; es decir, el promedio de todos los vectores contenidos en $B$ es $(1/2, \dots ,1/2)$ . ¿Cuál es el menor diámetro posible de un subconjunto equilibrado no vacío de $\{0,1\}^n$ ?

---

Resultados parciales

Deje que $d_n$ sea el mencionado diámetro más pequeño, y que $B$ ser un conjunto equilibrado que se da cuenta de ello. Sin perder la generalidad, $B$ contiene el vector cero $(0, \dots ,0)$ . Para ser equilibrado, también debe contener algún vector con más $1$ s que $0$ s. Por lo tanto $$ d_n \ge \left\lceil \frac {n+1}{2} \right\rceil \tag {1} $$ El producto cartesiano de dos conjuntos equilibrados está equilibrado, y su diámetro es la suma de los diámetros de sus factores. Por lo tanto, la secuencia $(d_n)$ es subaditivo: $$ d_{m+n} \le d_m+d_n \tag2 $$ (lo que en particular implica que $d_n/n$ tiene un límite.)

Los valores de $d_n$ Lo sé hasta ahora: $$ \begin {array}{|c|c|} \hline n & d_n \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 4 \\ \hline \end {array} $$

La mayor parte de la tabla se obtiene de $(1)$ - $(2)$ con la ayuda del ejemplo $$ \begin {pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end {pmatrix} $$ donde las columnas forman un conjunto equilibrado de diámetro $2$ mostrando $d_3 \le 2$ . (Por cierto, esto es un tetraedro inscrito en un cubo.)

Para $d_5$ los límites $(1)$ - $(2)$ dar $3 \le d_5 \le 4$ . Para ver que el diámetro no puede ser $3$ noten que WLOG un conjunto equilibrado de diámetros $3$ contiene las siguientes columnas: $$ \begin {pmatrix} 0 & 1 \\ 0 & 1 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \end {pmatrix} $$ Dado que el número total de $0$ s y $1$ s en las dos últimas filas debe ser el mismo, necesitamos una columna que termine con dos $1$ s: $$ \begin {pmatrix} 0 & 1 & * \\ 0 & 1 & * \\ 0 & 1 & * \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end {pmatrix} $$ pero no importa cómo se llenen los asteriscos, el diámetro es mayor que $3$ .

Answer 1

Esta es sólo una respuesta parcial. Tenemos tres resultados, y en los dos primeros se alcanza el límite inferior dado por (1):

$\bf (I)$ $d_{10}=6$ , $d_{11}=6$ , $d_{12}=7$ .

$\bf (II)$ $d_{2^k-2}=2^{k-1}$ , $d_{2^k-1}=2^{k-1}$ y $d_{2^k}=2^{k-1}+1$ , para $k>1$ .

$\bf (III)$ $d_{4k+1}\ge 2k+2$ para $k>0$ .

Sospecho que se pueden encontrar conjuntos cíclicos como los siguientes para cada $n=4k+3$ pero no fui capaz de encontrarlos, excepto por $k=0,1,2$ . Esto podría probar $d_{4k+2}=d_{4k+3}=2k+2$ y $d_{4k+4}=2k+3$ es decir, el mínimo diámetro posible.

Por otro lado (II) proporciona una familia infinita con $d_{n}$ mínimo.

$\bf Proof\ of\ (I):$ Esto se deduce del siguiente conjunto de 12 vectores en $\left(\Bbb{Z}/2\Bbb{Z}\right)^{11}$ : $$ \small\left\{ \begin{pmatrix}0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{pmatrix}, \begin{pmatrix}1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ \end{pmatrix}, \begin{pmatrix}0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ \end{pmatrix}, \begin{pmatrix}0\\ 0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\\ \end{pmatrix}, \begin{pmatrix}0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ \end{pmatrix}, \begin{pmatrix}1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\\ 0\\ \end{pmatrix}, \begin{pmatrix}0\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\\ \end{pmatrix}, \begin{pmatrix}1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 0\\ 1\\ \end{pmatrix}, \begin{pmatrix}1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 0\\ \end{pmatrix}, \begin{pmatrix}0\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ \end{pmatrix}, \begin{pmatrix}1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ \end{pmatrix}, \begin{pmatrix}1\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 1\\ \end{pmatrix}, \right\} $$ Como cada vector (excepto el primero) tiene 6 veces el 1, la distancia al primero es 6. Como todos los demás vectores son permutaciones cíclicas del segundo vector basta con calcular 5 distancias para comprobar que la distancia es siempre 6.

$\bf Proof\ of\ (II):$ Ahora demostramos $d_{2^k-2}=2^{k-1}$ , $d_{2^k-1}=2^{k-1}$ y $d_{2^k}=2^{k-1}+1$ . Esto se deduce de la existencia de un conjunto equilibrado de vectores $W^{(k)}=\{W_0^{(k)},\dots,W_{2^{k+1}-1}^{(k)}\}\subset \left(\Bbb{Z}/2\Bbb{Z}\right)^{2^{k}}$ con $d(W_{i}^{(k)},W_{j}^{(k)})=2^{k}$ para todos $k\ge 0$ .

De hecho, podemos definir $W_i^{(k)}$ de forma inductiva. Necesitamos la siguiente proposición que demostraremos a continuación:

$\bf Proposition:$ Existe un conjunto equilibrado de vectores $\{V_0^{(k)},\dots,V_{2^{k+1}-1}^{(k)}\}\subset \left(\Bbb{Z}/2\Bbb{Z}\right)^{2^k}$ tal que $d(V_{2j}^{(k)},V_{2j+1}^{(k)})=2^k$ y $d(V_{j}^{(k)},V_{i}^{(k)})=2^{k-1}$ si $i\ne j$ y $\{i,j\}\ne \{2t,2t+1\}$ para todos $t$ . Tenemos $V_0^{(0)}=0$ y $V_1^{(0)}=1$ .

Ahora, ponte $W_{0}^{(0)}=0$ y $W_{0}^{(0)}=1$ . Definir inductivamente $$ W_{2i}^{(k+1)}=\binom{V_{2i}^{(k+1)}}{W_i^{(k)}}\quad\text{and}\quad W_{2i+1}^{(k+1)}=\binom{V_{2i+1}^{(k+1)}}{W_i^{(k)}}. $$ Entonces, claramente $\left\{W_{i}^{(k+1)}\right\}_i$ está equilibrada,

$$ d(W_{2i}^{(k+1)},W_{2i+1}^{(k+1)})=d(V_{2i}^{(k+1)},V_{2i+1}^{(k+1)}))=2^{k+1} $$ y para $i\ne j$ y $\varepsilon_1,\varepsilon_2\in\{0,1\}$ tenemos $$ d(W_{2i+\varepsilon_1}^{(k+1)},W_{2j+\varepsilon_2}^{(k+1)})=d(V_{2i+\varepsilon_1}^{(k+1)},V_{2j+\varepsilon_2}^{(k+1)}))+d(W_{i}^{(k)},W_{j}^{(k)}) =2^{k}+2^{k}=2^{k+1}. $$ $$\tag*{$ \N - Caja $}$$ $\bf Proof\ of \ the \ Proposition:$ Sólo damos la fórmula inductiva, los detalles se pueden demostrar por inducción. Definir $$ V_{4i}^{(k+1)}=\binom{V_{2i}^{(k)}}{V_{2i}^{(k)}},\quad V_{4i+2}^{(k+1)}=\binom{V_{2i+1}^{(k)}}{V_{2i+1}^{(k)}+\Bbb{I}}\quad\text{and}\quad V_{2i+1}^{(k+1)}=V_{2i}^{(k+1)}+\Bbb{I}, $$ donde $\Bbb{I}$ es el vector con todas las entradas iguales a 1, y la suma está en $\Bbb{Z}/2\Bbb{Z}$ .

Para la prueba por inducción de que $d(V_i^{(k+1)},V_j^{(k+1)})=2^k$ si $i\ne j$ y $\{i,j\}\ne \{2t,2t+1\}$ para todos $t$ , hay que considerar los tres casos siguientes:

a) $\lfloor\frac{i}{4}\rfloor=\lfloor\frac{j}{4}\rfloor$ (aquí basta con considerar el caso $i\equiv 0\mod 2$ , $j\equiv 2\mod 2$ y el caso $i\equiv 0\mod 2$ , $j\equiv 2\mod 3$ ).

b) $\lfloor\frac{i}{4}\rfloor\ne \lfloor\frac{j}{4}\rfloor$ y $i\equiv j\mod 2$ (en este caso se sigue fácilmente por inducción).

c) $\lfloor\frac{i}{4}\rfloor\ne \lfloor\frac{j}{4}\rfloor$ y $i\not\equiv j\mod 2$ . Por ejemplo, si $i=2t$ y $j=2s+1$ entonces $$ d(V_i^{(k+1)},V_j^{(k+1)})= d(V_t^{(k)},V_s^{(k)}+\Bbb{I})+d(V_t^{(k)}+\varepsilon_1 \Bbb{I},V_s^{(k)}+\varepsilon_2 \Bbb{I})=2d(V_t^{(k)},V_s^{(k)})=2^k, $$ desde $\{s,t\}\ne \{2r,2r+1\}$ para todos $r$ . $$\tag*{$ \N - Caja $}$$

Damos los primeros valores de $V^{(k)}$ y $W^{(k)}$ . $$ V^{(0)}=\{0,1\},\quad W^{(0)}=\{0,1\},\quad $$ $$ V^{(1)}=\left\{\binom{0}{0},\binom{1}{1},\binom{1}{0},\binom{0}{1}\right\},\quad W^{(1)}=\left\{\begin{pmatrix}0\\ 0\\ 0 \end{pmatrix},\begin{pmatrix}1\\ 1\\ 0\end{pmatrix},\begin{pmatrix}1\\ 0\\ 1\end{pmatrix},\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}\right\} $$ $$ V^{(2)}=\left\{\begin{pmatrix}0\\ 0\\ 0\\ 0 \end{pmatrix},\begin{pmatrix}1\\ 1\\ 1\\ 1 \end{pmatrix},\begin{pmatrix}1\\ 1\\ 0\\ 0 \end{pmatrix},\begin{pmatrix}0\\ 0\\ 1\\ 1 \end{pmatrix},\begin{pmatrix}1\\ 0\\ 1\\ 0 \end{pmatrix},\begin{pmatrix}0\\ 1\\ 0\\ 1 \end{pmatrix},\begin{pmatrix}0\\ 1\\ 1\\ 0 \end{pmatrix},\begin{pmatrix}1\\ 0\\ 0\\ 1 \end{pmatrix}\right\}\quad $$ (nota que $W^{(2)}$ es el conjunto encontrado por A. Roberts) $$ W^{(2)}=\left\{\begin{pmatrix}0\\ 0\\ 0\\ 0 \\ 0\\ 0\\ 0\end{pmatrix},\begin{pmatrix}1\\ 1\\ 1\\ 1 \\ 0\\ 0\\ 0\end{pmatrix},\begin{pmatrix}1\\ 1\\ 0\\ 0 \\ 1\\ 1\\ 0\end{pmatrix},\begin{pmatrix}0\\ 0\\ 1\\ 1 \\ 1\\ 1\\ 0\end{pmatrix},\begin{pmatrix}1\\ 0\\ 1\\ 0 \\ 1\\ 0\\ 1\end{pmatrix},\begin{pmatrix}0\\ 1\\ 0\\ 1 \\ 1\\ 0\\ 1\end{pmatrix},\begin{pmatrix}0\\ 1\\ 1\\ 0 \\ 0\\ 1\\ 1\end{pmatrix},\begin{pmatrix}1\\ 0\\ 0\\ 1 \\ 0\\ 1\\ 1\end{pmatrix}\right\}\quad $$ y $V^{(3)}$ viene dada por $$ \tiny{\left\{\begin{pmatrix}0\\ 0\\ 0\\ 0 \\ 0\\ 0\\ 0\\ 0 \end{pmatrix},\begin{pmatrix}1\\ 1\\ 1\\ 1 \\ 1\\ 1\\ 1\\ 1 \end{pmatrix}, \begin{pmatrix}1\\ 1\\ 1\\ 1 \\ 0\\ 0\\ 0\\ 0 \end{pmatrix},\begin{pmatrix}0\\ 0\\ 0\\ 0 \\ 1\\ 1\\ 1\\ 1 \end{pmatrix}, \begin{pmatrix}1\\ 1\\ 0\\ 0 \\ 1\\ 1\\ 0\\ 0 \end{pmatrix}, \begin{pmatrix}0\\ 0\\ 1\\ 1\\ 0\\ 0 \\ 1 \\ 1 \end{pmatrix},\begin{pmatrix}0\\ 0\\ 1\\ 1\\ 1\\ 1\\ 0\\ 0 \end{pmatrix}, \begin{pmatrix}1\\ 1\\ 0\\ 0\\ 0\\ 0\\ 1\\ 1 \end{pmatrix}, \begin{pmatrix}1\\ 0\\ 1\\ 0 \\ 1\\ 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix}0\\ 1\\ 0\\ 1\\ 0\\ 1\\ 0 \\ 1\end{pmatrix}, \begin{pmatrix}0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix}1\\ 0\\ 1\\ 0\\ 0\\ 1\\ 0\\ 1 \end{pmatrix}, \begin{pmatrix}0\\ 1\\ 1\\ 0 \\ 0\\ 1\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix}1\\ 0\\ 0\\ 1 \\ 1\\ 0\\ 0\\ 1 \end{pmatrix},\begin{pmatrix}1\\ 0\\ 0\\ 1 \\ 0\\ 1\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 1\\ 1\\ 0 \\ 1\\ 0\\ 0\\ 1 \end{pmatrix}\right\}} $$

$\bf Proof\ of\ (III):$ Ahora demostramos $d_{4k+1}\ge 2k+2$ para $k>0$ . Supongamos por contradicción que $d_{4k+1}= 2k+1$ (nótese que por ( $1$ ) no podemos tener $d_{4k+1}<2k+1$ ).

Ahora, WLOG un conjunto equilibrado de diámetro $2k+1$ contiene las siguientes columnas: $$ \begin{pmatrix} 0 & 1 \\ \vdots & \vdots \\ 0 & 1 \\ 0 & 0 \\ \vdots & \vdots \\ 0 & 0 \end{pmatrix}, $$ donde la segunda columna tiene $2k+1$ veces la entrada $1$ y $2k$ veces la entrada $0$ . Dado que el número total de $0$ s y $1$ s en el último $2k$ las filas deben ser las mismas, necesitamos una columna que tenga al menos $k+1$ veces $1$ en el último $2k$ filas. Pero entonces esta columna puede tener como máximo $k$ veces el $1$ en la parte superior, por lo que la distancia a la segunda columna es al menos $k+1+k+1=2k+2$ , una contradicción que demuestra (III). $$\tag*{$ \N - Caja $}$$

$\bf Edit:$

Buscando vectores cíclicos encontré la siguiente construcción. Sea $p$ sea primo con $p\equiv 3\mod 4$ . Sea $J_p=\{k\in \Bbb{Z}/p\Bbb{Z},\ s.t.\ \exists x\in \Bbb{Z}/p\Bbb{Z}\ with\ x^2=k\}$ . Entonces hay $(p+1)/2$ elementos en $J_p$ . Definir los vectores $V_0,\dots V_{p-1}$ en $\left(\Bbb{Z}/2\Bbb{Z}\right)^p$ por: $$ (V_k)_i=\left\{\begin{array}{cc} 1&\text{ if $i-k\in J_p$}\\ 0&\text{ if $i-k\notin J_p$} \end{array} \right. $$ Entonces el conjunto $\{\vec{0},V_0,\dots,V_{p-1}\}$ es un conjunto equilibrado de vectores.

La siguiente conjetura se ha verificado para $p=3,7,11,19,23$ : $$ {\bf (IV)}\qquad\qquad d(V_i,V_j)=\frac{p+1}2\quad\text{for $ i\ne j $.} $$ Para $j=i+1$ la igualdad (IV) se puede demostrar utilizando la ley de reciprocidad cuadrática.

Si reunimos toda la información obtenida de (I), (II), (III) y (IV), y utilizando ( $2$ ) tenemos

$$ \begin{array}{|c|c|} \hline n & d_n \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 4 \\ 7 & 4 \\ 8 & 5 \\ 9 & 6 \\ 10 & 6 \\ 11 & 6 \\ 12 & 7 \\ 13 & 8 \\ 14 & 8 \\ 15 & 8 \\ 16 & 9 \\ 17 & 10 \\ 18 & 10 \\ 19 & 10 \\ 20 & 11 \\ 21 & 12 \\ 22 & 12 \\ 23 & 12 \\ 24 & 13 \\ 25 & 14 \\ 26 & 14 \\ 27 & ? \\ 28 & ? \\ 29 & 16 \\ 30 & 16 \\ 31 & 16 \\ 32 & 17 \\ 33 & 18 \\ 34 & 18 \\ 35 & ? \\ \hline \end{array} $$

Answer 2

(Probablemente esto sería mejor como comentario que como respuesta, pero parece que todavía no puedo comentar).

Creo que puedo mejorar ligeramente sus resultados parciales, con $d_7=4$ y (por tanto) $d_8=5$ . (Ya que siempre que $d_{2k-1} = k$ sus límites $(1)$ - $(2)$ dar $d_{2k}=k+1$ .)

Para la primera afirmación, basta con encontrar un conjunto equilibrado con diámetro igual a $4$ y parece que $$\left\{ \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{pmatrix} \right\}$$ es exactamente un conjunto de este tipo.

Answer 3

Esta es la respuesta simplificada (incompleta) que retoma todos los resultados de mi otra respuesta (e incluye algunos resultados obtenidos por Michelle). No creo que el problema general se resuelva a corto plazo.

En primer lugar, mejoramos el límite inferior de $d_n\ge \lceil\frac{n+1}{2}\rceil$ dado en (1) en la OP:

$\bf{Proposition\ 1:(III)}$ $d_{4k+1}\ge 2k+2$ para $k>0$ .

Así que tenemos un límite inferior que se puede describir módulo 4:

$n=4k$ , $d_n\ge b_{4k}=2k+1$ para $k>0$ .

$n=4k+1$ , $d_n\ge b_{4k+1}=2k+2$

$n=4k+2$ , $d_n\ge b_{4k+2}=2k+2$

$n=4k+3$ , $d_n\ge b_{4k+3}=2k+2$

Obtenemos la siguiente tabla para los límites inferiores: $$ \begin{array}{|c|c|} \hline n & b_n \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 4 \\ 7 & 4 \\ 8 & 5 \\ 9 & 6 \\ 10 & 6 \\ 11 & 6 \\ 12 & 7 \\ 13 & 8 \\ 14 & 8 \\ 15 & 8 \\ 16 & 9 \\ 17 & 10 \\ 18 & 10 \\ 19 & 10 \\ 20 & 11 \\ 21 & 12 \\ 22 & 12 \\ 23 & 12 \\ 24 & 13 \\ 25 & 14 \\ 26 & 14 \\ \vdots&\vdots\\ \hline \end{array} $$

$\bf{Proposition\ 2:}$ Si para algunos $j$ tenemos $d_{4j+3}=b_{4j+3}=2j+2$ entonces $d_n=b_n$ para $n\in\{4j+1,4j+2,4j+4,4j+5,8j+5,8j+6\}$ .

La prueba se deduce directamente de los límites inferiores y de (2) en el PO: $d_{n+m}\le d_n+d_m$ .

En vista de esta proposición, para establecer $d_n=b_n$ para todos $n$ basta con demostrarlo para $n=4j+3$ para todos $j$ .

Demostraremos la igualdad sólo para $4j+3=p$ un primo, $4j+3=p(p+2)$ un producto de primos gemelos o $4j+3=2^t-1$ para algunos $t$ . Esto demuestra, por ejemplo, que $d_n=b_n$ para todos $n\le 50$ excepto $n\in\{27,28,39,40\}$ .

Describiremos una construcción de conjuntos equilibrados de vectores de longitud $4j+3$ de diámetro $2j+2$ fuera de un cíclico $(v,k,\lambda)$ conjunto de diferencias con parámetros $(v,k,\lambda)=(4j+3,2j+1,j)$ demostrando así que siempre que exista tal conjunto de diferencias, tenemos $d_{4j+3}=b_{4j+3}=2j+2$ . Se sabe que tales conjuntos cíclicos existen para los tres casos mencionados anteriormente (Ver https://oeis.org/A217332 ). Para los demás casos de $n=4j+3$ se sabe que no existen tales conjuntos de diferencias cíclicas para $n\le 10000$ pero eso no implica que no haya conjuntos equilibrados de diámetro $2j+2$ Por lo tanto, estos casos siguen abiertos.

${\bf{Definition}}$ Un cíclico $(v,k,\lambda)$ conjunto de diferencias $D$ es un conjunto de $k$ residuos módulo $v$ tal que para cada residuo no nulo $s\mod v$ la ecuación $x-y\equiv s \mod v$ tiene exactamente $\lambda$ pares de soluciones $(x,y)$ con $x,y\in D$ . En particular, los conjuntos de diferencias Hadamard cíclicos tienen los parámetros $v=4j+3$ , $k=2j+1$ y $\lambda=j$ para un número entero no negativo $j$ .

Ahora defina los vectores $V_0,\dots,V_{v-1}\in\{0,1\}^v$ por $$ (V_s)_t=\left\{\begin{array}{cc} 0&\text{ if $t-s\in D$}\\ 1&\text{ if $t-s\notin D$} \end{array} \right. $$

${\bf{Claim:}}$ El conjunto $\{\vec{0},V_0,\dots,V_{v-1}\}$ es un conjunto equilibrado de vectores de diámetro $2j+2$ .

Es sencillo comprobar que el conjunto está equilibrado. Además, $$ d(\vec{0},V_s)=\#\{t, \ (V_s)_t=1\}=v-\# D=4j+3-( 2j+1)=2j+2, $$ y $d(V_s,V_i)=d(V_0,V_{|s-i|})$ por lo que basta con demostrar que $d(V_0,V_s)=2j+2$ para todos $s\ne 0$ .

Ahora arreglar $s$ y observe que $$ d(V_0,V_s)=\#\{t, \ (V_0)_t\ne (V_s)_t\} $$ $$=\quad\#\{t,\ (V_0)_t=0\text{ and }(V_s)_t=1\}\quad +\quad \#\{t,\ (V_0)_t=1\text{ and }(V_s)_t=0\}. $$ Definimos $$ A_{10}=\{t,\ (V_0)_t=1\text{ and }(V_s)_t=0\} $$ $$ A_{01}=\{t,\ (V_0)_t=0\text{ and }(V_s)_t=1\} $$ $$ A_{00}=\{t,\ (V_0)_t=0\text{ and }(V_s)_t=0\} $$ $$ A_{11}=\{t,\ (V_0)_t=1\text{ and }(V_s)_t=1\}. $$ Entonces $$ \# A_{10}+\# A_{00}=\#D=2j+1\quad\text{and}\quad \# A_{01}+\# A_{00}=\#D=2j+1, $$ y así $$ \# A_{10}=\# A_{01}=2j+1-\# A_{00}. $$ Pero $$ A_{00}=\{t,\ (V_0)_t=0\text{ and }(V_s)_t=0\}=\{t,\ t\in D\text{ and }t-s\in D\}, $$ y así $$ \# A_{00}=\#\{t, \ (t,t-s)\in D^2 \}=\{(x,y)\in D^2,\ x-y=s\} $$

Pero, por definición, la ecuación $x-y\equiv s \mod v$ tiene exactamente $\lambda=j$ pares de soluciones $(x,y)$ con $x,y\in D$ Por lo tanto $\# A_{00}=j$ y así $$ d(V_0,V_s)=\# A_{10}+\# A_{01}=2(2j+1-\# A_{00})=2j+2, $$ como se desee.

Podemos decir algo sobre $\lim_{n\to\infty} \frac {d_n}{n}$ . Por el lema de subaditividad de Fekete y (2) en la OP, el límite $\lim_{n} \frac{d_n}n$ existe. Así que el hecho de que haya infinitos números para los que se alcanza el límite inferior (por ejemplo, $2^t1$ ) implica $\lim_{n} \frac{d_n}n =\frac 12$ .

Por último, supongamos que la siguiente variante de la conjetura de Goldbach es cierta:

Todo número de la forma $4k+2$ es la suma de dos primos $p,q$ de la forma $4k+3$ .

Sabemos que $d_p=\frac{p+1}2$ y $d_q=\frac{q+1}2$ . Por lo tanto, si esta conjetura es cierta, el límite inferior se alcanza en cada número de la forma $4k+2$ y en cada número de la forma $4k+1$ .