1.7: Teoría Combinatoria de Números

Hay muchas preguntas interesantes que se encuentran entre la teoría de números y el análisis combinatorio. Consideramos primero uno que se remonta a I. Schur (1917) y está relacionado de manera sorprendente con el último teorema de Fermat. En términos generales, el teorema de Schur establece que si n es fijo y suficientemente muchos enteros consecutivos 1, 2, 3,. se separan en n clases, entonces al menos una clase contendrá elementos\(a\),\(b\),\(c\) con\(a + b = c\).

Consideremos el hecho de que si separamos los enteros positivos menos que\(2^n\) en\(n\) clases poniendo 1 en la clase 1, el siguiente 2 en la clase 2, el siguiente 4 en la clase 3, etc., entonces ninguna clase contiene la suma de dos de sus elementos. Alternativamente, podríamos escribir cada entero m en forma\(2^k \theta\) donde\(\theta\) es impar, y colocar\(m\) en la clase\(k\) th. Nuevamente los números menores que\(2^n\) estarán en\(n\) las clases y si\(m_1 = 2^k \theta_1\) y\(m_2 = 2^k \theta_2\) están en clase\(k\) entonces\(m_1 +m_2 = 2^k(\theta_1 + \theta_2)\) se encuentra en una clase numerada más alta. La forma más complicada de distribuir enteros que se describe a continuación nos permite distribuir 1, 2,...,\(\dfrac{3^n−1}{2}\) en\(n\) clases de tal manera que ninguna clase tiene una solución para\(a + b = c\):

1 2 5
3 4 6
10 11 7
13 12 8
.
...
...

Por otra parte, el teorema de Schur establece que si se separan los números 1, 2, 3,.,.,\([n! e]\) en\(n\) clases de cualquier manera entonces al menos una clase contendrá una solución a\(a + b = c\). La brecha entre las dos últimas declaraciones revela un interesante problema sin resolver, a saber, ¿se puede reemplazar el\([n! e]\) en el resultado de Schur por un número considerablemente menor? Los dos primeros ejemplos dados muestran que ciertamente no podemos ir tan bajo como\(2n − 1\), y el último ejemplo muestra que no podemos ir tan bajo como\(\dfrac{3^n−1}{2}\).

Ahora damos una definición y hacemos varias observaciones para facilitar la prueba del teorema de Schur.

Vamos\(T_0 = 1\),\(T_n = nT_{n−1} + 1\). Se comprueba fácilmente que

\(T_n = n! (1 + \dfrac{1}{1!} + \dfrac{2}{2!} \cdot\cdot\cdot + \dfrac{1}{n!}) = [n!e].\)

Así, el teorema de Schur se puede replantear de la siguiente manera: Si 1, 2,..., se\(T_n\) separan en\(n\) clases de cualquier manera lo que sea, al menos una clase contendrá una solución de\(a + b = c\). Esto lo demostraremos asumiendo que los números 1, 2,...,\(T_n\) han sido clasificados n vías sin clase que contenga una solución de\(a + b = c\) y de esto obtengan una contradicción. Tenga en cuenta que la condición\(a + b \ne c\) significa que ninguna clase puede contener la diferencia de dos de sus elementos.

Supongamos que alguna clase, digamos\(A\), contiene elementos\(a_1 < a_2 < \cdot\cdot\cdot\). Formamos diferencias de estos de la siguiente manera:

\(b_1 = a_2 - a_1, b_2 = a_3 - a_1, b_3 = a_4 - a_1, ...\)
\(c_1 = b_2 - b_1, c_2 = b_3 - b_1, c_3 = b_4 - b_1, ...\)
\(d_1 = c_2 - c_1, d_2 = c_3 - c_1, d_3 = c_4 - c_1, ...\)

y así sucesivamente. Observamos que todos los\(b\)'s,\(c\)'s,\(d\)'s, etc., son diferencias de\(a\)'s y por lo tanto no pueden estar en\(A\).

Ahora, comenzamos con\(T_n\) elementos. Al menos

\(\lfloor \dfrac{T_n}{n} + 1 \rfloor = T_{n - 1} + 1\)

de estos deben estar en una sola clase, digamos\(A_1\). Entonces\(T_{n - 1}\)\(b\) formamos. Estos no se encuentran en\(A_1\), y por lo tanto se encuentran en las\(n - 1\) clases restantes. Al menos

\(\lfloor \dfrac{T_{n - 1}}{n - 1} + 1 \rfloor = T_{n - 1} + 1\)

de ellos deben estar en una sola clase, digamos\(A_2\). Forman sus\(T_{n - 2}\) diferencias, las\(c\)'s. Estos\(T_{n - 2}\) números de rendimiento ni en\(A_1\) ni en\(A_2\). Continuando de esta manera arroja\(T_{n - 3}\) números no en\(A_1, A_2, A_3\). De esta manera finalmente obtenemos\(T_0 = 1\) número no perteneciente a\(A_1, A_2, ..., A_n\). Pero todos los números formados están entre los números\(1, 2, ..., T_n\) así que tenemos una contradicción, lo que prueba el teorema.

Afirmamos, sin pruebas, la conexión con el último teorema de Fermat. Una aproximación natural al teorema de Fermat sería tratar de demostrar que\(x^n + y^n = z^n\) (mod\(p\)) es insoluble módulo algunos\(p\), siempre y cuando\(p\) no se divida\(x \cdot y \cdot z\). Sin embargo, el teorema de Schur se puede utilizar para demostrar que este método debe fallar y de hecho si\(p > n!e\) entonces\(x^n +y^n = z^n\) (mod\(p\)) tiene una solución\(p\) sin un factor de\(xyz\).

Algo relacionado con el teorema de Schur es un famoso teorema de Van der Waerden, que investigamos brevemente. A principios de la década de 1920 surgió el siguiente problema en relación con la teoría de la distribución de residuos cuadráticos. Imagínese el conjunto de todos los enteros a dividir de cualquier manera en dos clases. ¿Se puede afirmar que se pueden encontrar progresiones aritméticas de longitud arbitraria es al menos una de estas clases? El problema permaneció sin resolver durante varios años a pesar de los esfuerzos concentrados de muchos matemáticos destacados. Finalmente fue resuelto en 1928 por Van der Waerden. Como no es raro con tales problemas, el primer paso de Van der Waerden fue hacer que el problema fuera más general, y por lo tanto más fácil.

Van der Waerden demostró lo siguiente: Dados enteros\(k\) y\(\ell\), existe un entero\(W = W(k, \ell)\) tal que si los números 1, 2, 3,...,\(W\) se separan en\(k\) clases de cualquier manera, entonces al menos una clase contendrá l términos en progresión aritmética. Aquí no vamos a dar la prueba de Van der Waerden. Es extremadamente complicado, difícil de ver a través, y solo lleva a un límite fantásticamente grande para W (k, l). Por esta razón, el lector podría considerar el muy útil problema sin resolver de encontrar una prueba alternativa más simple que\(W(k, \ell)\) existe y encontrar límites razonables para ello. Tendremos un poco más que decir sobre la función\(W(k, \ell)\) un poco más tarde.

Nuestro siguiente problema de la teoría combinatoria de números trata de secuencias “no promediadoras”. Llamamos a una secuencia\(A: a_1 < a_2 < a_3 < \cdot\cdot\cdot\) sin promediar si no contiene el promedio de dos de sus elementos, es decir,\(a_i + a_j \ne 2a_k\) (\(i \ne j\)). Deje que A (n) denote el número de elementos en\(A\) no exceder\(n\). El principal problema es estimar qué tan grande\(A(n)\) puede ser si no\(A\) está promediando. Podemos formar una secuencia sin promediar comenzando con 1, 2,... y luego tomando siempre el número más pequeño que no viole la condición para conjuntos sin promediar. De esta manera obtenemos 1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31,.... Es un dato interesante que esta secuencia está relacionada con el famoso conjunto ternario Cantor. En efecto, lo dejamos como un ejercicio para probar que esta secuencia se puede obtener sumando 1 a cada entero cuya representación en base 3 contiene sólo 0's y 1's. Esta secuencia es máxima en el sentido de que no se puede insertar un nuevo número en la secuencia sin destruir su carácter sin promediar. Esto, así como otros hechos, llevaron a Szekeres (alrededor de 1930) a conjeturar que este conjunto era tan denso como cualquier conjunto sin promediar. Para este conjunto, la función de conteo se puede estimar fácilmente para ser\(\thicksim n^{\log 2 / \log 3}\). Por lo tanto, llegó como una considerable sorpresa cuando Salem y Spencer (1942) demostraron que se podía tener un conjunto sin promediar de enteros\(\le n\) que contengan al menos\(n^{1 - c/\sqrt{\log\log n}}\) elementos.

Dado un número\(x\), escrito en base diez, decidimos si\(x\) está adentro con base\(R\) en las siguientes reglas.

Primero encerramos\(x\) en un juego de corchetes, poniendo el primer dígito (contando de derecha a izquierda) en el primer corchete, los dos siguientes en el segundo corchete, los tres siguientes en el tercer corchete, y así sucesivamente. Si el último corchete no vacío (el corchete más alejado a la izquierda que no consiste enteramente en ceros) no tiene un número máximo de dígitos, lo rellenamos con ceros. Por ejemplo, los números

\(a = 32653200200\),\(b = 100026000150600\),\(c = 1000866600290500\)

se pondría entre corchete

\(a = (00003)(2653)(200)(20)(0),\)
\(b = (10002)(6100)(150)(60)(0),\)
\(c = (10008)(6600)(290)(50)(0),\)

respectivamente. Ahora supongamos que el\(r^{\text{th}}\) paréntesis\(x\) contiene dígitos distintos de cero, pero todos los corchetes adicionales a la izquierda son 0. Llamar al número representado por los dígitos en el\(i^{\text{th}}\) paréntesis\(x_i\),\(i = 1, 2, ..., r - 2\). Además, denotar por\(\bar{x}\) el número representado por el dígito en los dos últimos paréntesis tomados en conjunto, pero excluyendo el último dígito. Para\(x\) pertenecer\(R\) requerimos

1. el último dígito de\(x\) debe ser 1,
2. \(x_i\)debe comenzar con 0 para\(i = 1, 2, ..., r - 2,\)
3. \(x_1^2 + \cdot\cdot\cdot x_{r - 2}^2 = \bar{x}.\)

En particular, tenga en cuenta que a satisface (2) pero viola (1) y (3) por lo que no\(a\) está en\(R\); sino\(b\) y\(c\) satisface las tres condiciones y están en\(R\). Para verificar (3) nosotros no eso\(60^2 + 150^2 = 26100\).

A continuación demostramos que no hay tres enteros en\(R\) progresión aritmética. Primero tenga en cuenta que si dos elementos de\ 9R\) tienen un número diferente de corchetes no vacíos su promedio no puede satisfacer (1). Por lo tanto, solo necesitamos considerar promedios de elementos de\(R\) tener el mismo número de corchetes no vacíos. De (1) y (3) se deduce que los dos elementos de se\(R\) pueden promediar entre corchetes para los primeros\(r − 2\) soportes y también para los dos últimos corchetes tomados juntos. Así, en nuestro ejemplo,

\(\dfrac{1}{2} (60 + 50) = 55, \dfrac{1}{2} (150 + 290) = 220,\)
\(\dfrac{1}{2} (100026100 + 100086600) = 100056350,\)
\(\dfrac{1}{2} (b + c) = (10005)(6350)(220)(55)(0)\)

Esto viola (3) y así no está en\(R\). En general vamos a demostrar que si\(x\) y\(y\) están en\(R\) entonces\(\bar{z} = \dfrac{1}{2} (x + y)\) viola (3) y así no está en\(R\).

Desde\(x\) y\(y\) están en\(R\),

\(\bar{z} = \dfrac{\bar{x} + \bar{y}}{2} = \sum_{i = 1}^{r - 2} \dfrac{x_i^2 + y_i^2}{2}.\)

Por otro lado,\(z\) en\(R\) implica

\(\bar{z} = \sum_{i = 1}^{r - 2} z_i^2 = \sum_{i = 1}^{r - 2} \dfrac{(x_i + y_i)^2}{2}.\)

Por lo tanto, si\(z\) está en\(R\) entonces

\(\sum_{i = 1}^{r - 2} \dfrac{x_i^2 + y_i^2}{2} = \sum_{i = 1}^{r - 2} \dfrac{(x_i + y_i)^2}{2}.\)

Así

\(\sum_{i = 1}^{r - 2} \dfrac{(x_i - y_i)^2}{2} = 0,\)

lo que implica\(x_i = y_i\) para\(i = 1, 2, ..., r - 2\). Esto junto con (1) y (2) implica eso\(x\) y no\(y\) son distintos.

La secuencia de Szekeres inicia con 1, 2, 4, 5, 10, 11,.... Nuestra secuencia comienza con

100000, 1000100100, 1000400200,...

Sin embargo, los términos de esta secuencia son eventualmente mucho más pequeños que los términos correspondientes de la secuencia de Szekeres. Ahora estimamos cuántos enteros\(R\) contienen exactamente\(r\) paréntesis. Dados\(r\) corchetes podemos hacer el primer dígito en cada uno de los\(r - 2\) paréntesis 0. Podemos llenar los primeros\(r - 2\) corchetes de manera arbitraria. Esto se puede hacer en

\(10^{0 + 1+ 2 + \cdot\cdot\cdot + (r - 2)} = 10^{\dfrac{1}{2} (r - 1)(r - 2)}\)

maneras. Los dos últimos corchetes se pueden rellenar de tal manera que satisfagan (1) y (3).

Para ver esto solo necesitamos verificar que los dos últimos paréntesis no se llenarán en exceso, y que el último dígito, que pondremos igual a 1, no será interferido. Esto se desprende de la desigualdad

\((10^1)^2 + (10^2)^2 + \cdot\cdot\cdot + (10^{r - 2})^2 < 10^{2(r - 1)}.\)

Para un dado\(n\) let\(r\) ser el entero determinado por

\[10^{\dfrac{1}{2}r(r + 1)} \le n < 10^{\dfrac{1}{2}(r + 1)(r + 2)}.\]

Dado que todos los enteros con como máximo\(r\) corchetes no excederán\(n\), y dado que los\(r\) corchetes se pueden llenar a especificación de\(10^{\dfrac{1}{2} (r - 2)(r - 1)}\) maneras, tenemos

\[R(n) \ge 10^{\dfrac{1}{2} (r - 2)(r - 1)}\]

Desde el lado derecho de (7.1) tenemos

\(r + 2 > \sqrt{2 \log n}\)

de manera que (7.2) implica que

\(R(n) \ge 10^{\dfrac{1}{2} (r - 2)(r - 1)} > 10^{\log n - c\sqrt{\log n}} > 10^{(\log n)(1 - c/\sqrt{\log n})}\)

donde todos los troncos están a la base 10.

Una vieja conjetura fue esa\(\dfrac{A(n)}{n} \to 0\) para cada secuencia sin promediar. Esto sólo ha sido probado recientemente (1954) por K. F. Roth. Su prueba no es elemental.

L. Moser ha utilizado una técnica similar para obtener límites más bajos para la función Van der Waerden\(W(k, \ell)\). Demostró que\(W(k, \ell) > \ell k^{\log k}\), es decir, mostró cómo distribuir los números, 1, 2,...,\([\ell k^{\log k}]\) en\(k\) clases de tal manera que ninguna clase contiene 3 términos en progresión aritmética. Usando un método bastante diferente Erdo\(\ddot{o}\) s y Rado lo han demostrado\(W(k, \ell) > \sqrt{2 \ell k^{\ell}}\).

Erd\(\ddot{o}\) s ha planteado la siguiente pregunta: ¿Cuál es el número máximo de enteros\(a_1 < a_2 < \cdot\cdot\cdot < a_k \le n\) tal que\(2^k\) las sumas\(a\) de distintas son todas distintas? Los poderes de 2 muestran que uno puede dar\(k + 1\)\(a\) no excediendo\(2^k\) y uno puede de hecho dar\(k + 2\)\(a\) bajo el\(2^k\) cumplimiento de la condición requerida. Por otro lado, todas las sumas involucradas son menores que\(kn\) para que

\[2^k \le kn,\]

lo que implica

\[k < \dfrac{\log n}{\log 2} + (1 + o(1)) \dfrac{\log \log n}{\log 2}.\]

Ahora mostramos cómo Erd\(\ddot{o}\) s y Moser mejoraron estas estimaciones (Nota del editor: El mejor límite inferior actual se puede encontrar en I. Aliev, “El lema de Siegel y conjuntos distintos de suma”, Discrete Comput. Geom. 39 (2008), 59—66.) a

\[2^k < 4\sqrt{k} n,\]

lo que implica

\[k < \dfrac{\log n}{\log 2} + (1 + o(1)) \dfrac{\log \log n}{2\log 2}.\]

La conjetura de Erd\(\ddot{o}\) s es que

\[k = \dfrac{\log n}{\log 2} + o(1).\]

Denote la suma\(a\) de distintos por\(s_1, s_2, ..., s_{2^k}\) y let\(A = a_1 + a_2 + \cdot\cdot\cdot a_k\). Observe que la suma promedio es\(\dfrac{A}{2}\) ya que podemos emparejar cada suma con la suma del conjunto complementario. Esto sugiere que estimamos\(\sum_i (s_i - \dfrac{A}{2})^2\).

Tenemos

\(\sum_i (s_i - \dfrac{A}{2})^2 = \sum \dfrac{1}{2}(\pm a_1 \pm a_2 \pm \cdot\cdot\cdot \pm a_k)^2,\)

donde la última suma recorre las\(2^k\) posibles distribuciones de signo. Al cuadrar nos encontramos con que todos los términos cruzados vienen en pares mientras que cada uno\(a_i^2\) aparecerá\(2^k\) veces. Así

\(\sum_i (s_i - \dfrac{A}{2})^2 = 2^k \sum a_i^2 < 2^{k - 2} n^2 k.\)

Así, el número de sumas\(s_i\) para las cuales

\(|s_i - \dfrac{A}{2}| \ge n \sqrt{k}\)

no puede exceder\(2^{k - 1}\). Como todas las sumas son diferentes, tenemos números\(2^{k - 1}\) distintos en un rango de longitud\(2n \sqrt{k}\). Esto rinde\(2^{k - 1} \le 2n \sqrt{k}\) según se requiera.

Dejar\(a_1 < a_2 < ...\) ser una secuencia infinita de enteros y\(f(n)\) definir como el número de soluciones de\(n = a_i + a_j\) donde todas las soluciones cuentan una vez. G. A. Dirac y D. J. Newman dieron las siguientes pruebas interesantes que\(f(n)\) no pueden ser constantes de alguna etapa en adelante. Si\(f(\ell + 1) = f(\ell + 2) = \cdot\cdot\cdot\) hubiéramos

\(\dfrac{1}{2} (\sum a^{a_k})^2 + \sum z^{2a_k} = \sum f(n) z^n\)
\(= P_{\ell} (z) + a\dfrac{z^{\ell + 1}}{1 - z}, \ \ \ \ \ (f(\ell + 1) = a),\)

donde\(P(z)\) es un polinomio de grado\(\le \ell\). Si\(z \to -1\) en el eje real el lado derecho permanece acotado, pero el lado izquierdo se acerca al infinito, ya que ambos términos del lado izquierdo son positivos, y el segundo tiende al infinito. Esta contradicción prueba el teorema.

Turan y y Erd\(\ddot{o}\) s conjeturaron que si\(f(n) > 0\) por todos suficientemente grandes\(n\) entonces lim sup\(f(n) = \infty\) pero esto parece muy difícil de probar. Una conjetura aún más fuerte sería que si\(a_k > ck^2\) entonces lim sup\(f(n) = \infty\). El resultado más conocido en esta dirección es solo lim sup\(f(n) \ge 2\).

Fuchs y Erdös demostraron recientemente que

\(\sum_{k = 1}^{n} f(k) = cn + o(\dfrac{n^{\dfrac{1}{4}}{\log n})\)

es imposible. Si\(a_k = k^2\) se llega al problema de los puntos de celosía en un círculo de radio\(n\). Aquí Hardy y Landau demostraron

\(\sum_{k = 1}^n f(k) = \pi n + o(n \log n)\)

no se sostiene. Aunque no tan fuerte como esto, el resultado de Erd\(\ddot{o}\) s y Fuchs es aplicable a una situación mucho más general y es mucho más fácil (pero no muy fácil) de probar.

Dejar\(a_1 < a_2 < \cdot\cdot\cdot\) ser una secuencia infinita de enteros. Erd\(\ddot{o}\) s conjeturó, y G. G. Lorentz demostró, que existe una secuencia\({b_i}\) de densidad cero tal que cada entero es de la forma\(a_i + b_j\).

Un problema interesante sin resolver en esta línea es encontrar una secuencia\(B\):\(b_1 < b_2 < \cdot\cdot\cdot\) con función de conteo\(B(n) < \dfrac{cn}{\log n}\) tal que cada entero sea de la forma\(2^k + b_j\).

Dejar\(a_1 < a_2 < \cdot\cdot\cdot < a_{2n}\) ser\(2n\) enteros en el intervalo\([1,4n]\) y\(b_1 < b_2 < \cdot\cdot\cdot < b_{2n}\) los números restantes en el intervalo. Erd\(\ddot{o}\) s conjeturó que existe un entero\(x\) tal que el número de soluciones de\(a_i + x = b_j\) es al menos\(n\). Es bastante fácil demostrar que existe una para\(x\) que el número de soluciones de\(a_i + x = b_j\) sea al menos\(\dfrac{n}{2}\). Nos limitamos a observar que el número de soluciones de\(a_i + y = b_j\) es\(4n^2\) y que hay 8n opciones posibles de\(y\), es decir,\(−4n \le y \le 4n\),\(y \ne 0\). Así para algunos\(y_0\) hay al menos\(\dfrac{n}{2}\)\(b\)'s en\(a_i + y_0\) como se ha dicho.

P. Scherk mejoró el\(\dfrac{n}{2}\) to\(n(2 - \sqrt{2}) = .586n\). Por un método completamente diferente L. Moser mejoró esto más a\(.712n\). Por otro lado Selfridge, Ralston y Motzkin han utilizado S.W.A.C. para desmentir la conjetura original y han encontrado ejemplos donde ningún número es representable más de\(.8n\) veces como una diferencia entre an\(a\) y\(a\)\(b\).

Otro conjunto de problemas interesantes de la teoría combinatoria de números gira sobre el concepto de cadena de adición introducido por A. Scholz. Una cadena de suma para\(n\) es un conjunto de enteros\(1 = a_0 < a_1 < \cdot\cdot\cdot < a_r = n\) tal que cada elemento\(a_p\) puede escribirse como una suma\(a_{\sigma} + a_{\tau}\) de elementos anteriores de la cadena. Por ejemplo para\(n = 666\)

1, 2, 4, 8, 16, 24, 40, 80, 160, 320, 640, 664, 666

formar una cadena con\(r = 12\); lo mismo vale para

1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 324, 648, 666.

En todo caso debemos tener\(a_1 =2\),\(a_2 = 3\) y/o 4. Por la longitud\(\ell = \ell(n)\) Scholtz entiende lo más pequeño\(\ell\) para el que existe una cadena de adición\(a_0, a_1, ..., a_{\ell} = n\).

Scholtz declaró lo siguiente:

\(m + 1 \le \ell(n) \le 2m\)para\(2^m + 1 \le n \le 2^{m + 1}\) (\(m \ge 1\));
\(\ell(ab) \le \ell(a) + \ell(b);\)
\(\ell (2^{m + 1} - 1) \le m + \ell (m + 1).\)

Los dos primeros de estos son fáciles de probar. El tercero conjeturaríamos ser falso. Scholtz supuso que el primero podría mejorarse y planteó la cuestión de si

\(1 \le \text{lim sup}_{n \to \infty}\ \dfrac{\ell(n)}{\log_2 n} \le 2\)

podría mejorarse.

En lo que sigue probamos (1) y esbozamos una prueba debido a A. Brauer que

\(\ell(n) \thicksim \log_2 n.\)

Supongamos que los enteros están escritos en base 2 y buscamos una cadena de suma para 10110110 digamos. Podríamos formar la cadena

1, 10, 100, 101, 1010, 1011, 10110, 101100, 101101, 1011010,
1011011, 10110110, 101101100, 101101101.

En este proceso, cada dígito “cuesta” como máximo dos elementos en la cadena para que eso\(\ell < 2 \log_2 n\). Dado que el lado izquierdo de la desigualdad de (1) es trivial el método sugerido anteriormente arroja una prueba de (1).

La idea de Brauer es construir primero un gran stock de números y usarlo cuando surja la ocasión. Supongamos que\(n\) se trata\(2^m\). Empezamos con la cadena 1, 2,...\(2^r\), donde se\(r\) determinará más adelante. Ahora podemos dividir los dígitos de\(n\) en\(m/r\) bloques con\(r\) dígitos en cada bloque. Por ejemplo, supongamos

\(n = (101)(110)(010)(101)(111)\)

Aquí\(m = 15\),\(r = 3\).

Comenzando con nuestro stock de todos los números de 3 dígitos podemos proceder de la siguiente manera:

1, 10, 100,\(\underline{101}\), 1010, 10100, 101000,\(\underline{101110}\),
1011100, 10111000, 101110000,\(\underline{101110010}\),...

donde entre las etapas subrayadas duplicamos y en las etapas subrayadas agregamos el número apropiado de nuestro stock para construir\(n\). En este caso necesitaríamos\(2^3 + 2^{15} + 5\) pasos. En general, el número de pasos para un número bajo\(2^m\) sería aproximadamente\(2^r + m + \dfrac{m}{c}\). Por elección apropiada de\(r\) podríamos hacer\(2^r + \dfrac{m}{r}\) lo pequeño que nos plazca en comparación con\(m\). En efecto, usando esta idea Brauer demostró en general

\(\ell (n) < \log_2 n {1 + \dfrac{1}{\log \log n} + \dfrac{2 \log 2}{(\log n)^{1 - \log 2}} }.\)