Есть ли доказательство что нижняя граница

[erwins]

преобразование Фурье есть n*ln(n) и есть ли вероятность что возможен шаг похожий на сортировку Хола

как и в случае обычной сортировки, преобразование Фурье на произвольном кольце имеет порядок n*ln(n)

в тоже время, если в сортировке добавить требование конечности кольца, то удается получить порядка n*ln(ln(n))*2^(ln*(n)) что значительно меньше.