О степени ограничений функций q -значной логики на линейные многообразия | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/2

В случае конечного поля F_q степень ограничения функции q -значной логики от n переменных на линейное многообразие размерности r векторного пространства F_qⁿ определена как степень полинома от r переменных, представляющего данное ограничение. Для многообразий фиксированной размерности оценена вероятность появления у функции ограничений степени не выше заданной, а также получена асимптотика числа многообразий, на которых ограничения аффинны. Показано, что при n → ∞ для почти всех функций q -значной логики от n переменных значение максимальной размерности линейного многообразия, на котором ограничение аффинно, принадлежит отрезку [Llog_qn + Iog_q log_qnJ, P∣og_qn + log_qlog_qnJ], в то время как аналогичный параметр для случая фиксации переменных находится в пределах [LlogqnJ, LlogqnJ].