О представимости целых чисел значениями функции Рамануджана

конъюнкции Ks. Чтобы обнаружить неисправность, надо найти набор, на котором K's ф Ks равно 1 или, что то же самое, K's ф Ks равно 1.

Если K's = 1, то неисправность обнаруживается на наборе ¿¿i = (0, 0,... , 0). Если K s = 0, то неисправность обнаруживается на наборе ¿73 = (1,1,... ,1).

Пусть, наконец, K's не константа. Тогда существует переменная Xi, которая входит в конъюнкцию Ks и не входит в K's. Переменная xn нам может понадобиться только в случае поломки последнего конъюнктора цепи, но тогда на выходе "сломанной" цепи будет константа, а этот случай уже рассмотрен. Можем не рассматривать переменную xi, так как она может понадобиться только при поломке самого верхнего элемента цепи, но на него подаются две переменные и мы можем выбрать другую переменную (если это xn, то на выходе "сломанной" цепи будет константа, а этот случай уже рассмотрен). Поэтому на имеющемся в T наборе с единственным нулем в г-м разряде (во всех остальных разрядах этого набора единицы) получаем K's ф Ks = 1. Неисправность будет обнаружена. Тем самым мы показали, что T является единичным проверяющим тестом для схемы S. Его длина равна n +1, что даже меньше, чем n + 3. Неизбыточность очевидна (в ходе перебора всех неисправностей мы не получали тривиальной функции неисправности). Теорема в случае г = 1 доказана.

СПИСОК ЛИТЕРАТУРЫ

1. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

2. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Тр. Матем. ин-та АН СССР. 1958. 51. 270-360.

3. Яблонский С.В. Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, Физматлит, 1988, 5-25.

4. Редькин Н.П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.

5. Редькин Н.П. Дискретная математика. М.: Физматлит, 2009.

6. Яблонский С.В. Введение в дискретную математику. 2-е изд. М.: Наука, 1986.

7. Reddy S.M. Easily testable realization for logic functions // IEEE Trans. Comput. 1972. N 1. 124-141.

Поступила в редакцию 04.03.2011

УДК 511.34

О ПРЕДСТАВИМОСТИ ЦЕЛЫХ ЧИСЕЛ ЗНАЧЕНИЯМИ ФУНКЦИИ РАМАНУДЖАНА

П. В. Снурницын1

Доказано, что каждое целое число представляется суммой 7940 значений функции Рамануджана.

Ключевые слова: аналитическая теория чисел, функция Рамануджана, проблема Ва-ринга.

It is proved that every integer number can be expressed as a sum of 7940 values of the Ramanujan tau function.

Key words: analytic number theory, Ramanujan tau function, Waring's problem.

Настоящая работа посвящена аддитивной задаче, связанной с функцией Рамануджана, а именно

исследуется вопрос о разрешимости для любого целого числа N уравнения вида

g

Ет N,

i=1

1 Снурницын Павел Владимирович — асп. каф. математического анализа мех.-мат. ф-та МГУ, e-mail: snurnitsyn@gmail.com.

где т(п) — функция Рамануджана. Напомним, что функция т Рамануджана может быть определена как коэффициент разложения

«П (! - ^)24 = Е т(п)яП

п=1 п=1

(см., например, [1]).

В работах [2, 3] М. З. Гараев, В. К. Гарсия, С. В. Конягин доказали разрешимость уравнения (1) при

д = 74000 с оценкой тах^^дЩ |ЛПП и ПРИ 9 = 148000 с оценкой так^^дЩ \N\ne 1о8ь8|лг|; где с > 0 — абсолютная постоянная.

В данной статье получен следующий результат.

Теорема. Для любого целого числа N уравнение ^т(пг) = N 'разрешимо в натуральных числах

—

Пг, . . . , П7940, причем таХ1^7940 Щ < |ЛГ| 11 .

Таким образом, множество значений функции Рамануджана образует аддитивный базис множества целых чисел порядка 7940.

Доказательство проводится по схеме, предложенной в работе [2]. Пусть М — достаточно большое четное число, Ро = М~, Р = {р : р простое, 23 < р ^ Ро}> — подмножество Р наибольшей мощности, такое, что £ 6=1 т (р'г) = £ т (р'г) при любых р[,... ,р'и е Р', р[ < ... < р'6, р'7 < ... < р'и, (р[, ...,р'6) = (р7,... ,р''2). В [2] показано, что подмножество Р' существует и

\Р'\ "С Мтт~тз2.

а

Обозначим Р = [Р0], Ъ = \ogPi Ф = МЬ~2. Для дроби — с д ^ Ь2, а < д, (а, (?) = 1 определим

Множества О,(а, д) не пересекаются. Разобьем интервал [—1 — следующим образом:

0= У П(а,д), ш = [-1;1-1]\0.

д^Ь2,а<Я

(а,д)=1

Пусть

где е(х) = е2пгх.

Лемма 1. При г > 23

Б (а) = ^ е(ар11), 3 (М) = ! Б(а)г е(-аМ)йа,

Г(^)7, М~1Г~1 / М~1Г~1 1оё1оёМ-'г(^г) (1оёМу + 1(1оёму 1оёМ ,

где &(М) — особый ряд проблемы Варинга-Гольдбаха для степени 11. При этом существует постоянная Со, такая, что &(М) ^ Со > 0, Со не зависит от М. Доказательство см. в [4, 5].

Лемма 2. При а € и для Б(а) справедлива оценка Б(а) <С , где р = 1/17630.

Доказательство см. в [4].

Лемма 3. Для достаточно большого четного М уравнение ^2=' р'1 = М разрешим,о в числах р',...,р215 е Р\Р'.

Доказательство. Рассмотрим уравнение

р11 + ... + р11 + и!1 + ... + и11 + п1\1 + ... + и" = М,

где pi,... ,pr £ P, ui,us+i £ Ui,us,U2S £ Us, r ^ 24, s — натуральное число, значение которого будет

1-— 1- —

выбрано ниже, % = {и : и G & \ , P¿ < и < 2P¿}, 1 < i < s, Рг = \PQ, Р2 = \РХ 11, ..., Ps = t^-i" • Заметим, что \Ui\ х Pj (logP¿)-1.

Пусть I(M) — число решений уравнения (3). Тогда

i-i

I(M) = у S(a)rTi(a)2 ... Ts(a)2e(-aM)da = j S(a)rTi(a)2 ... Ts(a)2e(-aM)da,

где

тг(а) = ^ е(аи11), 1 < г < иеи

Разобьем промежуток интегрирования, получим I(М) = Д(М) + !г(М), где

Ь(М) = ! Б (а)г Т1(а)2 ...Т3(а)2 е(-аМ)йа, 12 (М) = ^ Б(а)г Т1(а)2 ...Т3(а)2 е(-аМ)йа. п ш

Для 12 (М) имеем оценку

1

|12(М)| < тах|Б(а)|г /Т1(а)2 ...Т3(а)2(1а.

а£ш J

\2 гр

i 1ци

0

Интеграл в правой части не превосходит |Ui| ... |Us|. По лемме 2

(log M)r ' Рассмотрим Ii (M):

Ii (M )= £ ••• £ J (M - ui1-----uii).

Из леммы 1 получаем, что при r ^ 24

о MÎT7-"1 о mît7-"1 log log M

v 7 Vl 1 1 17 (logM)r Vl 1 1 17 (logM)r log M '

где Ci,C2 — постоянные. Учитывая, что

(log M)s 1 11 "'1 (log M)s '

имеем

KM > С М2~2ф3 _ с M2-2(tt)s Мтг^-i log log М _ М^-рУ

^ 5 (log M)2s (log M)r 6 (log M)2s (log M)r log M 7 (log M)s (log M)r '

При s = 95 получаем оценки

M_Lr+i_4 M_Lr+i_4

C\log МУ+™ < J

где rj = 2(if)95.

Рассмотрим уравнение (3) при г = 25. Пусть 1'(М) — число решений этого уравнения, а 1''(М) — число таких решений, что по крайней мере одно £ Р'. Для 1'(М) из (4) при г = 25 получаем оценку снизу

1<м> » <* (Ь^'

А для I"(М) из (4) при г = 24 и (2) получаем оценку сверху

, МТ!"4 М тт-ч-ш

Таким образом, I'(М) > 1''(М), и уравнение

Р1 + ... + Р25 + и1!1 + ... + п\10 = М разрешимо в числах р 1,... ,Р25 ,и 1,..., и 1 90 £ Р \ Р'. Лемма доказана.

Лемма 4. Для любого р £ Р \ Р' существуют р1,... ,р'ц £ Р', такие, что

6 11

Р11 = Е ТРР) - Е ТР'Р) - Т(Р2).

Д1 =

i=1 i=7

Доказательство см. в [2].

Лемма 5. Любое целое 'число r, 0 ^ r < 370944, представимо в виде r = ^^ т(ai), где ai ^ 105, 1 ^ i < 198.

Доказательство см. в [2].

Теорема следует из лемм 3-5. Отметим, что полученное улучшение результата работы [2] достигнуто за счет леммы 3. В работе [2] использовалась разрешимость уравнения Варинга-Гольдбаха 11 степени в числах из P\P' с числом слагаемых 2050.

Автор выражает благодарность научному руководителю профессору Г. И. Архипову за постановку задачи.

СПИСОК ЛИТЕРАТУРЫ

1. Iwaniec H. Topics in classical automorphic forms. Providence, RI: Grad. Stud. Math., Amer. Math. Soc., 1997.

2. Гараев М.З., Гарсиа В.С., Конягин С.В. Проблема Варинга с т-функцией Рамануджана // Изв. РАН. Сер. матем. 2008. 72, № 1. 39-50.

3. Garaev M.Z., Garcia V.C., Konyagin S.V. The Waring problem with the Ramanujan т-function. II // Canad. Math. Bull. 2009. 52, N 2. 195-199.

4. Виноградов И.М. Метод тригонометрических сумм в теории чисел. М.: Наука, 1980.

5. Хуа Ло-кен. Аддитивная теория простых чисел // Тр. Матем. ин-та АН СССР. 1947. 22. 3-179.

Поступила в редакцию 25.05.2011

УДК 519.95

ОБ ОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

А. А. Андреев1

Рассматривается задача о реализации функций многозначной логики формулами. Приводится метод получения сверхэкспоненциальных оценок сложности для последовательностей функций.

1 Андреев Александр Андреевич — студ. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: sanchez_14@mail.ru.