Диагностические тесты для дискретных функций, определённых на кольцах

В статье изучаются источники неисправностей, связанные с конечными коммутативными кольцами главных идеалов. Таблицы неисправностей таких источников соответствуют таблицам Кэли для умножения в кольцах, элементы которых заменяются значениями двоичной функции от них. Для таких колец естественным образом вводятся понятия диагностического теста и функции Шеннона длины диагностического теста. Показано, что если $A$ — кольцо главных идеалов, имеющее только один простой идеал $p \neq A$, и $p^n = 0$ для некоторого $n \in \mathbb {N}$, то функция Шеннона длины диагностического теста на этом кольце имеет вид $L^{{\rm diagn}}(A,n) = \Theta(n).$ Вводится понятие легкотестируемых функций, т. е. функций, относительно которых длина диагностического теста по порядку роста равна логарифму числа попарно не равных столбцов таблицы неисправностей. Показана связь между легкотестируемостью и отделимостью столбцов таблиц неисправностей для двух конкретных источников неисправностей.