1.7: Комбінаторна теорія чисел

Існує багато цікавих питань, які лежать між теорією чисел і комбінаторним аналізом. Розглянемо перший, який сходить до І.Щура (1917) і дивним чином пов'язаний з останньою теоремою Ферма. Грубо кажучи, теорема Шура стверджує, що якщо n є фіксованим і досить багато послідовних цілих чисел 1, 2, 3,.,. розділені на n класів, то принаймні один клас буде містити елементи\(a\),\(b\),\(c\) with\(a + b = c\).

Розглянемо той факт, що якщо розділити натуральні числа менше ніж\(2^n\) на\(n\) класи, поставивши 1 в клас 1, наступні 2 в класі 2, наступні 4 в класі 3 і т.д., то жоден клас не містить суми двох його елементів. Крім того, ми могли б записати кожне ціле число m у формі,\(2^k \theta\) де\(\theta\) непарно, і місце\(m\) в\(k\) му класі. Знову числа менше, ніж\(2^n\) будуть лежати в\(n\) класах, а якщо\(m_1 = 2^k \theta_1\) і\(m_2 = 2^k \theta_2\) знаходяться в класі,\(k\) то\(m_1 +m_2 = 2^k(\theta_1 + \theta_2)\) лежить у вищому пронумерованому класі. Більш складний спосіб розподілу цілих чисел, описаний нижче, дозволяє нам розподіляти 1, 2,...\(\dfrac{3^n−1}{2}\) на\(n\) класи таким чином, що жоден клас не має рішення\(a + b = c\):

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

З іншого боку, теорема Щура стверджує, що якщо\([n! e]\) розділити числа 1, 2, 3,., на\(n\) класи будь-яким чином, то принаймні один клас буде містити рішення\(a + b = c\). Розрив між двома останніми твердженнями виявляє цікаву невирішену проблему, а саме, чи можна замінити результат\([n! e]\) в Щурі на значно меншу кількість? Перші два наведені приклади показують, що ми, безумовно, не можемо йти так низько\(2n − 1\), як, і останній приклад показує, що ми не можемо йти так низько, як\(\dfrac{3^n−1}{2}\).

Тепер ми даємо визначення і зробимо кілька зауважень, щоб полегшити доказ теореми Щура.

Нехай\(T_0 = 1\),\(T_n = nT_{n−1} + 1\). Легко перевіряється, що

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

Таким чином, теорема Шура може бути передана наступним чином: Якщо 1, 2,...,\(T_n\) розділені на\(n\) класи будь-яким чином, принаймні один клас буде містити рішення\(a + b = c\). Доведемо це, припустивши, що числа 1, 2,...\(T_n\) були класифіковані n способами без класу, що містить розв'язку\(a + b = c\) і з цього отримати протиріччя. Зауважте, що умова\(a + b \ne c\) означає, що жоден клас не може містити різницю двох його елементів.

Припустимо, що якийсь клас, скажімо\(A\), містить елементи\(a_1 < a_2 < \cdot\cdot\cdot\). Ми формуємо відмінності від них наступним чином:

\(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, ...\)

і так далі. Ми\(b\) зауважимо, що всі,\(c\) 's,\(d\)' s, і т.д., є відмінностями і, отже, не може лежати в\(A\).\(a\)

Тепер почнемо з\(T_n\) елементів. Принаймні

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

з них повинні лежати в одному класі, скажімо\(A_1\). Потім ми\(T_{n - 1}\)\(b\) формуємо. Ці не лежать в\(A_1\), а отже, лежать в інших\(n - 1\) класах. Принаймні

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

з них повинні лежати в одному класі, скажімо\(A_2\). Сформувати їх\(T_{n - 2}\) відмінності\(c\), тобто ці\(T_{n - 2}\) числа прибутковості ні в\(A_1\) ні\(A_2\). Продовжуючи таким чином, дає\(T_{n - 3}\) цифри не в\(A_1, A_2, A_3\). Таким чином ми в кінцевому підсумку отримуємо\(T_0 = 1\) число, яке не належить\(A_1, A_2, ..., A_n\). Але всі числа, що утворюються, є серед чисел,\(1, 2, ..., T_n\) тому у нас є протиріччя, яке доводить теорему.

Ми без доказів констатуємо зв'язок з останньою теоремою Ферма. Природним підходом до теореми Ферма було б спробувати показати, що\(x^n + y^n = z^n\) (мод\(p\)) є нерозв'язним по модулю деякого, за умови\(p\), що\(p\) не ділиться\(x \cdot y \cdot z\). Однак теорема Шура може бути використана, щоб показати, що цей метод повинен зазнати невдачі, і справді, якщо\(p > n!e\) тоді\(x^n +y^n = z^n\) (мод\(p\)) має рішення з\(p\) не коефіцієнтом\(xyz\).

Дещо пов'язана з теоремою Шура відома теорема Ван дер Вердена, яку ми коротко досліджуємо. На початку 1920-х років виникла наступна проблема у зв'язку з теорією розподілу квадратичних залишків. Уявіть собі безліч цілих чисел, які потрібно розділити будь-яким чином на два класи. Чи можна стверджувати, що арифметичні прогресії довільної довжини можна знайти хоча б один з цих класів? Проблема залишалася невирішеною протягом декількох років, незважаючи на зосереджені зусилля багатьох видатних математиків. Остаточно вона була вирішена в 1928 році Ван дер Ваерден. Як це не рідкість з такими проблемами, перший крок Ван дер Ваердена полягав у тому, щоб зробити проблему більш загальною, а отже, і простіше.

Van der Waerden довів наступне: задані цілі числа\(k\) і\(\ell\), існує\(W = W(k, \ell)\) таке ціле число, що якщо числа 1, 2, 3,...\(W\) розділені на\(k\) класи будь-яким чином, то принаймні один клас буде містити l членів в арифметичній прогресії. Ми не будемо давати докази Ван дер Ваердена тут. Це надзвичайно складно, важко проглядається наскрізь, і призводить лише до фантастично великої межі для W (k, l). З цієї причини читач може розглянути дуже стоїть невирішену проблему пошуку альтернативного більш простого доказу, який\(W(k, \ell)\) існує, та пошуку розумних меж для цього. Про функцію нам доведеться трохи більше сказати\(W(k, \ell)\) трохи пізніше.

Наступна задача комбінаторної теорії чисел стосується «несередніх» послідовностей. Ми називаємо послідовність\(A: a_1 < a_2 < a_3 < \cdot\cdot\cdot\) неусереднений, якщо вона не містить середнє значення двох її елементів, тобто,\(a_i + a_j \ne 2a_k\) (\(i \ne j\)). Нехай A (n) позначають кількість елементів в\(A\) не перевищує\(n\). Основна проблема полягає в тому, щоб оцінити, наскільки великим\(A(n)\) може бути, якщо\(A\) це не усереднення. Ми можемо сформувати неусереднений послідовність, починаючи з 1, 2,... а потім завжди приймаючи найменше число, яке не порушує умову для неусереднених множин. Таким чином отримуємо 1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31,... Цікавим є той факт, що ця послідовність пов'язана зі знаменитим канторовским потрійним набором. Дійсно, ми залишаємо це як вправу, щоб довести, що ця послідовність може бути отримана шляхом додавання 1 до кожного цілого числа, представлення якого в базі 3 містить тільки 0 і 1. Ця послідовність є максимальною в тому сенсі, що жодне нове число не може бути вставлено в послідовність, не знищуючи її неусереднений характер. Це, як і інші факти, змусило Секереса (близько 1930 року) здогадатися, що цей набір був таким же щільним, як і будь-який неусереднений набір. Для цього набору функцію підрахунку можна легко оцінити як\(\thicksim n^{\log 2 / \log 3}\). Тому це стало значним сюрпризом, коли Салем і Спенсер (1942) довели, що можна мати неусереднений набір цілих чисел,\(\le n\) що містять принаймні\(n^{1 - c/\sqrt{\log\log n}}\) елементи.

З огляду на число\(x\), написане в основі десяти, ми вирішуємо, чи\(x\) є в\(R\), виходячи з наступних правил.

Спочатку укладаємо\(x\) в набір дужок, поставивши першу цифру (рахуючи справа наліво) в першу дужку, наступні дві в другу дужку, наступні три в третю дужку і так далі. Якщо остання непорожня дужка (найдальша ліворуч дужка, яка не складається повністю з нулів) не має максимальної кількості цифр, ми заповнюємо її нулями. Наприклад, цифри

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

було б в дужках

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

відповідно. Тепер припустимо,\(r^{\text{th}}\) дужка\(x\) містить ненульові цифри, але всі подальші дужки ліворуч 0. Викликати номер, представлений цифрами в\(i^{\text{th}}\) дужці\(x_i\),\(i = 1, 2, ..., r - 2\). Далі позначаємо числом,\(\bar{x}\) представленим цифрою в останніх двох дужках, взятих разом, але виключаючи останню цифру. Для\(x\) того, щоб належати,\(R\) ми вимагаємо

1. остання цифра\(x\) повинна бути 1,
2. \(x_i\)має починатися з 0 для\(i = 1, 2, ..., r - 2,\)
3. \(x_1^2 + \cdot\cdot\cdot x_{r - 2}^2 = \bar{x}.\)

Зокрема, зауважте, що a задовольняє (2), але порушує (1) і (3) так,\(a\) що не в\(R\); але\(b\) і\(c\) задовольняє всі три умови і знаходяться в\(R\). Щоб перевірити (3) ми не це\(60^2 + 150^2 = 26100\).

Далі ми доведемо, що немає трьох цілих чисел в\(R\) арифметичній прогресії. По-перше, зауважте, що якщо два елементи\ 9R\) мають різну кількість непорожніх дужок, їх середнє значення не може задовольнити (1). Таким чином, нам потрібно лише розглянути середні значення елементів,\(R\) що мають однакову кількість непорожніх дужок. З (1) і (3) випливає, що два елементи\(R\) можуть бути усереднені дужкою за кронштейном для перших\(r − 2\) дужок, а також для останніх двох дужок, взятих разом. Таким чином, в нашому прикладі,

\(\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)\)

Це порушує (3) і так не в\(R\). Загалом доведемо, що якщо\(x\) і\(y\) знаходяться в\(R\) то\(\bar{z} = \dfrac{1}{2} (x + y)\) порушує (3) і так не в\(R\).

Так як\(x\) і\(y\) знаходяться в\(R\),

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

З іншого боку,\(z\) в\(R\) має на увазі

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

Отже, якщо\(z\) є в\(R\) то

\(\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}.\)

Таким чином

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

що має на увазі\(x_i = y_i\) для\(i = 1, 2, ..., r - 2\). Це разом з (1) і (2) означає, що\(x\) і не\(y\) відрізняються.

Послідовність Секереса починається з 1, 2, 4, 5, 10, 11,... Наша послідовність починається з

100000, 1000100100, 1000400200,...

Тим не менш, члени цієї послідовності в кінцевому підсумку набагато менші, ніж відповідні члени послідовності Секереса. Тепер ми оцінюємо, скільки цілих чисел в\(R\) містять точно\(r\) дужки. За заданими\(r\) дужками ми можемо зробити першу цифру в кожній з\(r - 2\) дужок 0. Перші\(r - 2\) дужки ми можемо заповнити довільним чином. Це можна зробити в

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

способи. Останні дві дужки можна заповнити таким чином, щоб задовольнити (1) і (3).

Щоб переконатися в цьому нам потрібно лише перевірити, що останні дві дужки не будуть переповнені, і що остання цифра, яку ми поставимо рівною 1, не завадить. Це випливає з нерівності.

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

Для заданого\(n\)\(r\) нехай є ціле число, яке визначається

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

Оскільки всі цілі числа з найбільшою кількістю\(r\) дужок не перевищуватимуть\(n\), а оскільки\(r\) дужки можуть бути заповнені до специфікації\(10^{\dfrac{1}{2} (r - 2)(r - 1)}\) способами, ми маємо

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

З правого боку (7.1) ми маємо

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

так що (7.2) означає, що

\(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})}\)

де всі колоди мають підставу 10.

Стара гіпотеза полягала в тому, що\(\dfrac{A(n)}{n} \to 0\) для кожної неусереднений послідовності. Це було доведено зовсім недавно (1954) К.Ф. Рот. Його доказ не елементарний.

Л. Мозер використовував подібну техніку, щоб отримати нижчі межі для функції Ван дер Ваердена\(W(k, \ell)\). Він довів\(W(k, \ell) > \ell k^{\log k}\), що, тобто показав, як розподілити числа, 1, 2,...,\([\ell k^{\log k}]\) на\(k\) класи таким чином, що жоден клас не містить 3 членів в арифметичній прогресії. Використовуючи зовсім інший метод, Erdo\(\ddot{o}\) s і Rado показали, що\(W(k, \ell) > \sqrt{2 \ell k^{\ell}}\).

Erd\(\ddot{o}\) s підняв наступне питання: Яка максимальна кількість цілих чисел,\(a_1 < a_2 < \cdot\cdot\cdot < a_k \le n\) таких, що\(2^k\) суми різних різних?\(a\) Повноваження 2 показують, що можна дати\(k + 1\)\(a\) не перевищення,\(2^k\) і насправді можна дати\(k + 2\)\(a\) під\(2^k\) задоволення необхідної умови. З іншого боку, всі залучені суми менше, ніж\(kn\) так, що

\[2^k \le kn,\]

що має на увазі

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

Тепер ми покажемо, як\(\ddot{o}\) Ерд з і Мозер покращили ці оцінки (Примітка видавця: поточна найкраща нижня межа може бути знайдена в І.Алієві, «Лема Зігеля та різні набори», «Дискретні обчислення». Геом. 39 (2008), 59—66.) до

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

що має на увазі

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

Здогадка Erd\(\ddot{o}\) s полягає в тому, що

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

Позначимо суму\(a\) distinctin's by\(s_1, s_2, ..., s_{2^k}\) і нехай\(A = a_1 + a_2 + \cdot\cdot\cdot a_k\). Зверніть увагу, що середня сума полягає в\(\dfrac{A}{2}\) тому, що ми можемо поєднати кожну суму з сумою комплементарного множини. Це говорить про те, що ми оцінюємо\(\sum_i (s_i - \dfrac{A}{2})^2\).

У нас є

\(\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,\)

де остання сума проходить над\(2^k\) можливими розподілами знака. Після квадрата ми виявляємо, що всі перехресні умови приходять парами, тоді як кожен\(a_i^2\) буде з'являтися\(2^k\) раз. Таким чином

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

Таким чином, кількість сум,\(s_i\) на які

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

не може перевищувати\(2^{k - 1}\). Оскільки всі суми різні, у нас є\(2^{k - 1}\) різні числа в діапазоні довжини\(2n \sqrt{k}\). Це дає\(2^{k - 1} \le 2n \sqrt{k}\) в міру необхідності.

\(a_1 < a_2 < ...\)Дозволяти нескінченну послідовність цілих чисел і визначити,\(f(n)\) щоб бути кількість розв'язків,\(n = a_i + a_j\) де всі розв'язки розраховують один раз. Дж. Дірак і Дж. Ньюман дали наступний цікавий доказ, який\(f(n)\) не може бути постійним з якогось етапу. \(f(\ell + 1) = f(\ell + 2) = \cdot\cdot\cdot\)Якби ми мали

\(\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),\)

\(P(z)\)де - многочлен ступеня\(\le \ell\). Якщо\(z \to -1\) на дійсній осі права сторона залишається обмеженою, але ліва сторона наближається до нескінченності, так як обидва члени з лівого боку позитивні, а друга прагне до нескінченності. Це протиріччя доводить теорема.

Туран і Ерд\(\ddot{o}\) здогадалися, що якщо\(f(n) > 0\) для всіх досить великий,\(n\) то лайм суп,\(f(n) = \infty\) але це здається дуже важко довести. Ще сильнішою здогадкою було б те, що якщо\(a_k > ck^2\) тоді lim sup\(f(n) = \infty\). Найвідомішим результатом в цьому напрямку є тільки lim sup\(f(n) \ge 2\).

Нещодавно Фукс і Ердеш довели, що

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

неможливо. Якщо\(a_k = k^2\) доходить до задачі точок решітки по колу радіуса\(n\). Тут Харді і Ландау довели

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

не тримає. Хоча і не настільки сильний, як це, результат Erd\(\ddot{o}\) s і Fuchs застосовний до набагато більш загальної ситуації і набагато простіше (але не дуже легко) довести.

\(a_1 < a_2 < \cdot\cdot\cdot\)Дозволяти нескінченна послідовність цілих чисел. \(\ddot{o}\)Ерд з припустив, і Г.Г. Лоренц довів, що існує послідовність\({b_i}\) нульової щільності така, що кожне ціле число має вигляд\(a_i + b_j\).

Цікавою нерозв'язаною задачею в цих рядках є пошук послідовності\(B\):\(b_1 < b_2 < \cdot\cdot\cdot\) з функцією підрахунку\(B(n) < \dfrac{cn}{\log n}\) така, що кожне ціле число має вигляд\(2^k + b_j\).

\(a_1 < a_2 < \cdot\cdot\cdot < a_{2n}\)Дозволяти\(2n\) цілі числа в\(b_1 < b_2 < \cdot\cdot\cdot < b_{2n}\) інтервалі\([1,4n]\) і інші числа в інтервалі. \(\ddot{o}\)Ерд з припустив, що існує ціле число\(x\) таке, що кількість розв'язків\(a_i + x = b_j\) не менше\(n\). Це досить легко показати, що існує\(x\) так, що кількість рішень\(a_i + x = b_j\) є не менше\(\dfrac{n}{2}\). Ми просто спостерігаємо, що кількість рішень\(a_i + y = b_j\) є\(4n^2\) і що існує 8n можливих варіантів\(y\), тобто\(−4n \le y \le 4n\),\(y \ne 0\). Таким чином, для деяких\(y_0\) є принаймні в\(\dfrac{n}{2}\)\(b\),\(a_i + y_0\) як зазначено.

П.Щерк покращив\(\dfrac{n}{2}\) до\(n(2 - \sqrt{2}) = .586n\). Зовсім іншим методом Л. Мозер удосконалив це далі\(.712n\). З іншого боку Selfridge, Ralston і Motzkin використовували S.W.A.C. для спростування оригінальної гіпотези і знайшли приклади, де жодне число не представляється більш ніж\(.8n\) разів як різниця між\(a\) і\(a\)\(b\).

Ще один набір цікавих задач комбінаторної теорії чисел обертається навколо концепції ланцюга додавання, введеного А.Шольцем. Ланцюжок додавання для\(n\) - це набір цілих чисел\(1 = a_0 < a_1 < \cdot\cdot\cdot < a_r = n\) таким чином, що кожен елемент\(a_p\) може бути записаний як сума\(a_{\sigma} + a_{\tau}\) попередніх елементів ланцюга. Наприклад для\(n = 666\)

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

утворюють ланцюг з\(r = 12\); те ж саме тримає для

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

У будь-якому випадку ми повинні мати\(a_1 =2\), і\(a_2 = 3\) або 4. По довжині\(\ell = \ell(n)\) Шольц розуміє найменшу,\(\ell\) для якої існує ланцюжок додавання\(a_0, a_1, ..., a_{\ell} = n\).

Шольц заявив наступне:

\(m + 1 \le \ell(n) \le 2m\)для\(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).\)

Перші два з них легко довести. Третій ми б здогадалися, щоб бути помилковим. Шольц припустив, що перше можна вдосконалити і поставив питання про те, чи

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

можна було б вдосконалити.

У чому далі ми доведемо (1) і окреслимо доказ завдяки А.Брауеру, що

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

Припустимо, цілі числа записані в базі 2, і ми шукаємо ланцюжок додавання для 10110110 скажімо. Ми могли б сформувати ланцюжок

1, 10, 100, 101, 1010, 1011, 10110, 101100, 10101, 1011010,
1011011, 1011010, 10110100, 101101100, 101101101.

У цьому процесі кожна цифра «коштує» не більше двох елементів в ланцюжку так, що\(\ell < 2 \log_2 n\). Оскільки ліва частина нерівності (1) є тривіальною, запропонований вище метод дає доказ (1).

Ідея Брауера полягає в тому, щоб спочатку створити великий запас чисел і використовувати його, коли настає нагода. Припустимо\(n\), це приблизно\(2^m\). Починаємо з ланцюжка 1, 2,...\(2^r\), де\(r\) буде визначено пізніше. Тепер ми можемо розбити цифри на\(n\)\(m/r\) блоки з\(r\) цифрами в кожному блоці. Наприклад, припустимо

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

Ось\(m = 15\),\(r = 3\).

Починаючи з нашого запасу всіх 3-значних чисел, ми можемо діяти наступним чином:

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

де між підкресленими етапами ми подвоюємо і на підкреслених етапах додаємо відповідне число з нашого запасу для нарощування\(n\). У цьому випадку нам знадобляться\(2^3 + 2^{15} + 5\) кроки. Загалом, кількість кроків для числа під\(2^m\) буде приблизно\(2^r + m + \dfrac{m}{c}\). При відповідному виборі\(r\) ми могли б зробити\(2^r + \dfrac{m}{r}\) так мало, як нам заманеться в порівнянні з\(m\). Дійсно, використовуючи цю ідею, Брауер довів в цілому

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