Научный журнал
Успехи современного естествознания
ISSN 1681-7494
"Перечень" ВАК
ИФ РИНЦ = 0,653

ОБ ОДНОМ СВОЙСТВЕ РАВНОМЕРНОСТИ И НОВЫХ ЛПτ-ПОСЛЕДОВАТЕЛЬНОСТЯХ

Матусов И.Б. 1
1 Институт машиноведения РАН
В статье исследовано важное свойство равномерности, обеспечивающее равномерность начальных участков многомерных ЛПt-последовательностей. Доказано, что существуют такие начальные условия для первых столбцов направляющих матриц, что последовательность точек, построенная по последовательности всех взятых подряд моноциклических операторов, при любой размерности пространства обладает этим свойством. Доказано также, что можно конструировать ЛПτ-последовательность так, чтобы у направляющих матриц, соответствующих различным координатам ее точек, все угловые определители были равны I (mod 2).
равномерно распределенная последовательность
моноциклический оператор
направляющая матрица
1. Соболь И.М. Многомерные квадратурные формулы и функции Хаара. ‒ М.: Наука,. 1969. ‒ С. 288.
2. Соболь И.М. Точки, равномерно заполняющие многомерный куб. – М.: Знание, 1985. ‒ С. 125.

Последовательности многомерных точек, могут обладать различными свойствами равномерности [1].Сложность заключается в том, что для решения практических задач эти свойства должны выполняться уже при сравнительно небольших количествах точек. Только в этом случае данные последовательности могут быть успешно использованы при решении практических задач,относящихся к теории кубатурных формул, в задачах оптимизации, и т.д. С этой целью в [2] были сформулированы некоторые дополнительные требования к равномерно распределенным последовательностям, а также новые условия [1], обеспечивающие, как это показано в данной работе, существование ЛПτ-последовательностей.

Свойство А. Рассмотрим Кn – единичный n-мерный куб. Разобьем Кn плоскостями
хj = I/2 при j=I, 2, …n на t =2n октантов, которые будем считать двоичными параллелепипедами. Разобьем последовательность точек PI, I=1,… на двоичные участки, длина которых равна 2n: Р0, Рt-1,Pt, …, Р2t-1, Р2t, …, P3t-1, … . Если в любом из этих участков все точки принадлежат различным октантам, то мы говорим, что последовательность обладает свойством А.

Согласно [2] справедлива теорема: ЛПτ-последовательность Р0, Р1, …, PI, … обладает свойством А тогда и только тогда, когда определитель (размером n x n), составленный из первых столбцов всех направляющих матриц, равен I (mod 2).Данная теорема дает возможность строить ЛПτ-последовательности со свойством А. Однако остается открытым вопрос: можно ли в качестве последовательности моноциклических операторов {Lk} [1], по которым рассчитываются значения соответствующих координат точек ЛПτ последовательности, брать все операторы низших порядков. Вопрос обоснован тем, что именно в этом случае значение t будет минимальным, что наилучшим образом отразится на всех характеристиках равномерности. Для ответа на него рассмотрим следующие утверждения.

Пусть L1 , L2 , …, Ln – различные моноциклические операторы с порядками
m1, m2, …, mn соответственно.

Лемма 1. Пусть рj(I) – есть ДР – последовательности [1], соответствующие всем моноциклическим операторам низших порядков L1, … Ln. Пусть m - порядок оператора Ln. Тогда справедливо следующее неравенство:

matus5.wmf при m≥5  (1.1)

Доказательство. Доказательство проведем индукцией по m. При m=5 неравенство справедливо, т.к. максимальное n при этом равно 13 [2]. Пусть для некоторого m имеет место (1.1) при любом n, соответствующем данному m. Докажем, что при любом n, соответствующем m+I, будет выполняться аналогичное неравенство. Учитывая, что число моноциклических операторов порядка m+I равно matus6.wmf, (где j(k) – теоретико-числовая функция Эйлера, равная количеству натуральных чисел меньших k и взаимно простых с k) докажем, что

matus7.wmf.

Преобразуем данное неравенство следующим образом :

matus8.wmf.

Сравнивая его с (1.1), остается показать, что

matus9.wmf,

т.е. matus10.wmf. Очевидно, что

matus11.wmf.

Окончательно имеем

matus12.wmf,

т.е. приходим к очевидному неравенству, которое справедливо при m≥3.

Пусть m(n) – порядок моноциклического оператора, стоящего на n-м месте в последовательности всех моноциклических операторов, взятых подряд.

Лемма 2. Рассмотрим n-I последовательность элементов GF(2) {uI(k)}, k=1,…, n–1, I=0,1,2,… Пусть к данному набору принадлежит последовательность, состоящая из единиц, и пусть определитель

matus13.wmf.

Рассмотрим моноциклический оператор Ln порядка m≥ m(n), m≥5. Тогда существует такое решение оператора Ln – {uI(n)}, что определитель

matus15.wmf (1.2)

Доказательство. Допустим обратное: как-бы ни выбирать первые m значений решения оператора Ln определитель (1.2) равен 0 (mod 2). Т.к. столбцы предыдущего определителя линейно независимы, то первые n–I элементы последнего столбца в (1.2) единственным образом выразятся через эти столбцы. Но в силу указанного предположения, последний элемент n-го столбца в (1.2) должен таким же образом выражаться через элементы n-й строки, принадлежащие соответствующим столбцам в (1.2), при любом выборе первых m значений последней строки. Т.е. для последней строки имеем

matus16.wmf или (1.3)

matus17.wmf

(cI=0 при I < I0)

при произвольных, начинающихся с единицы, первых m значениях этой строки. Это означает, что любое решение моноциклического оператора Ln является решением линейного разностного оператора порядка n–I0

matus18.wmf.

Действительно, пусть matus19.wmf – решение моноциклического оператора Ln. Если в качестве последней строки в (1.2) взять любой участок этого решения, начинающийся с I, то получим (1.3). Возьмем произвольный участок длины n, начинающийся с нуля. Его, в силу того, что первые m значений можно выбирать произвольно, представим в виде суммы двух участков той же длины, начинающихся с I. А т.к. для этих участков выполняется (1.3), то (1.3) справедливо и для данного участка, начинающегося с 0. Т.е. при любых начальных значениях u1(n), u2(n), …, um(n) выполняется (1.3). А это и означает, что всякое решение моноциклического оператора Ln порядка m, является решением линейного разностного оператора L*(uI). Раз это так, то многочлен, соответствующий L*(uI) должен делиться на многочлен, соответствующий оператору Ln. Пусть

matus20.wmf (1.4)

многочлен над полем GF(2), соответствующий оператору L*. Покажем, что если многочлен, соответствующий Ln,

xm+am–1xm–1 + … + a1x+1  (1.5)

является делителем многочлена (1.4), то он будет делителем некоторого многочлена большей степени, у которого нет в качестве слагаемых одночленов вида хk, где k≤ m, за исключением I.

Пусть (1.4) содержит в качестве слагаемого некоторый одночлен хk. где k≤ m (т.е. аk = I).

Умножая (1.4) на хk +I, получим многочлен степени n–I0 + k, у которого коэффициент при хk , т.е. аk=0. Аналогично можно поступить с любым слагаемым степени не большей m. Получим многочлен, у которого степень предпоследнего члена больше m, а максимальная степень самого многочлена равна matus21.wmf, т.е.

matus22.wmf. (1.6)

Если многочлен (1.5) делит (1.4), то он должен делить и многочлен (1.6). С другой стороны (1.6), как и многочлен (1.4), содержит четное число слагаемых, т.к. по условию этой леммы одна из строк (1.2) состоит из единиц. Поэтому (1.6) можно представить в виде суммы двучленов (P>0)

matus23.wmf (1.7)

Разделим каждый из этих двучленов на (1.5). Т.к. (1.5) соответствует моноциклическому оператору Ln порядка m, то, согласно [1], является делителем двучлена (x2m-1+I), но не является делителем никакого двучлена xs+1, где s<2m–I. Но в силу леммы 1 степень многочлена (1.6) меньше 2m–I. Поэтому, разделив почленно (1.7) на (1.5), получим

matus24.wmf

где kI<m, k<m. Остаток от деления,
хk+ …+1≠0 (mod 2), т.к. при делении каждого из двучленов (1.7) на (1.5) остаток содержит 1.Двучленов – нечетное число, поэтому суммарный остаток также содержит I. Таким образом, многочлен (1.6) не делится на многочлен (1.5).Противоречие.

Теорема 1. Существуют такие начальные условия для первых столбцов направляющих матриц, что последовательность точек РI=(P1(I), … Pn(I)), построенная по последовательности всех взятых подряд моноциклических операторов, при каждом n обладает свойством А.

Доказательство. Доказательство проведем по индукции. Легко проверить, что теорема справедлива до n = 7 (m(8)=5). Пусть она справедлива при некотором n>7. Но это означает, что выполняются условия лем-
мы 2. И если рассмотреть любой моноциклический оператор Ln+1 , порядок которого такой же, как у Ln или на единицу больше, то в силу леммы 2 ,у решения этого оператора найдется начинающийся с I участок длины n+I, такой что

matus25.wmf (1.8)

При этом все угловые определители (1.8) равны I (mod 2). Как следует из [2], это доказывает справедливость теоремы при n+I. Теорема доказана.

Построение новых ЛПτ-последовательностей. В [1] приводится следующий результат. Если в качестве в матрицы направляющих числителей взять такую, у которой все угловые определители равны 1(mod 2), то определенная этой матрицей ДР – последовательность будет ЛП0-последовательностью.

Возникает вопрос нельзя ли из таких последовательностей, определяющих значения различных коордитат многомерных точек, построить ЛПτ-последовательность? Приводимые ниже результаты дают возможность обобщить на рассматриаемый случай теорему из [1], в которой приводится конструкция ЛПτ-последовательности.

Пусть L – моноциклический оператор порядка m. Рассмотрим последовательность операторов L, L2, Ln,… . Каждому оператору Ln в этой последовательности поставим в соответствии его m линейно независимых решений

matus27.wmf (2.1)

причем любое решение оператора Ln не является решением оператора Ln–1.

При этом первые nm элементов в каждой из последовательностей (2.1) выбраны так, чтобы в матрице

matus28.wmf (2.2)

все угловые определители были равны 1(mod 2). Положим, что matus29.wmf – произвольная степень отличного от L моноциклического оператора matus30.wmf

Лемма 1. Операторы matus31.wmf и Lk не имеют общих решений.

Доказательство. Действительно, пусть
{uI} – одна из последовательностей в (2.1) такая, что Lk(uI) =0. Тогда если бы имело место matus32.wmf (ui) =0, то Lk–1 matus35.wmf (ui) = matus37.wmf Lk–1 (ui) = 0. А это не так потому, что Lk–1(uI) – есть не тривиальное решение моноциклического оператора L. Вследствие леммы 4 параграфа 2 из [1], оно не может быть решением оператора matus40.wmf.

Лемма 2. Результат действия оператора matus41.wmf на любые n (nmatus42.wmfm) линейно независимые решения оператора Lk есть n линейно независимые решения оператора Lk–1.

Доказательство. Покажем сначала, что matus43.wmf сохраняет линейную независимость решений оператора Lk. Подействуем оператором matus44.wmf на n решений оператора Lk. Т.к. matus45.wmf линейный оператор, то линейная зависимость полученных решений означала бы, что matus46.wmfmatus47.wmf, I = 1,2,3,… .
Но matus48.wmf есть не тривиальное решение Lk в силу линейной независимости n выбранных решений. А т.к. решение Lk не может быть решением matus49.wmf,то полученные решения линейно независимы. Теперь подействуем оператором L на рассматриваемые решения оператора Lk. Понятно, что таким образом получим n решений оператора Lk–1. Они линейно независимы. Действительно, обратное означает, что

matus50.wmf.

Сумма matus51.wmf не есть решение оператора L, т.к. матрица (2.2) содержит все m линейно независимых решений оператора L. Если бы matus52.wmf была решением оператора L, то она выражалась бы линейно через эти m решений. Но это находится в противоречии с условием, что все угловые определители в (2.2) были равны 1(mod 2).

Теорема 2. Пусть L1, L2,…, Ln – различные моноциклические операторы, порядки которых равны m1, m2,…, mn. Каждому оператору Lk поставим в соответствие матрицу (matus58.wmf), аналогичную (2.2). Пусть {PI} – последовательность точек с координатами, определяемыми этими матрицами, в соответствии с [1]. Тогда PI= (P1(I),…, Pn(I)) – есть ЛПτ-последовательность в единичном кубе Kn со значениями

matus59.wmf.

Доказательство. Cогласно доказательству указанной выше теоремы 4 из [1], для того, чтобы произвольный двоичный участок последовательности длины 2v был Пτ-сеткой необходимо и достаточно, чтобы ранг матрицы

matus60.wmf, (2.3)

составленной из matus61.wmf столбцов матриц направляющих чисел, соответствующих различным моноциклическим операторам, был равен matus62.wmf. Обозначим через matus63.wmf остаток от деления matus64.wmf на mk так, что matus66.wmf.
Пусть matus67.wmf. Оставим в (2.3) первые m1 строк без изменений, а остальные будем заменять линейными комбинациями строк в соответствии с действием оператора L1. Получим эквивалентную матрицу

matus69.wmf. (2.4)

В верхнем углу, согласно условию теоремы, находится невырожденная матрица. Нетрудно видеть, что столбцы matus71.wmf,
matus72.wmf, являющиеся участками решений оператора L1, линейно независимы. Если matus73.wmf, то в нижней части матрицы (2.4) повторяем то же преобразование matus75.wmf раз. Если matus76.wmf, то после этих преобразований останутся matus77.wmf столбцов с элементами matus78.wmf. Перенесем их в конец матрицы. Получим следующую мат-
рицу

matus80.wmf (2.5)

Согласно лемме 2, matus82.wmf, matus83.wmf, есть участки решений оператора matus84.wmf.

В силу этой леммы, столбцы matus85.wmf, matus86.wmf, образуют матрицу

matus87.wmf,

определитель которой равен 1. Посредством L2 c нижней частью матрицы (2.5) (расположенной под В1) проделаем преобразования, аналогичные предыдущим. Оставшиеся matus88.wmf столбцов перенесем в конец матрицы. Проделав такие же преобразования со всеми Lk, получим матрицу

matus89.wmf (2.6)

Здесь matus90.wmf и элементы остаточной матрицы

matus91.wmf. (2.7)

Если бы все matus92.wmf были равны 0, то исходная матрица уже имела бы вид (2.6).

Ввиду того, что в (2.7) matus93.wmf, то matus94.wmf. Значит, столбцы остаточной матрицы – это участки решений моноциклических уравнений. Пусть среди matus95.wmf всего s чисел, отличных от нуля. Обозначим их через matus96.wmf, matus97.wmf Все решения matus98.wmf,
соответсвующие одному f, линейно независимы в силу леммы 2. 

matus99.wmf

Поэтому из леммы 7 параграфа 3 [1] следует, что все столбцы остаточной матрицы линейно независимы, т.е., что ее ранг равен matus100.wmf. А ранг всей матрицы равен matus101.wmf Теорема доказана.


Библиографическая ссылка

Матусов И.Б. ОБ ОДНОМ СВОЙСТВЕ РАВНОМЕРНОСТИ И НОВЫХ ЛПτ-ПОСЛЕДОВАТЕЛЬНОСТЯХ // Успехи современного естествознания. – 2014. – № 5-2. – С. 135-140;
URL: http://natural-sciences.ru/ru/article/view?id=33941 (дата обращения: 26.06.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252