Ultra-Euclidean functions invert the integers: ℤ carries none, and two settled cases of a conjecture of Sekhon

Abstract

Let R be an integral domain and f: Rsetminus{0} → ℤ_(≥ 0) a Euclidean function in the modern sense, so that submultiplicativity f(a) ≤ f(ab) is not assumed. Following Sekhon, call f ultra-Euclidean if f(a+b) ≤ max{f(a),f(b)} whenever a,b,a+b ≠ 0, and write widetilde(f)(a)=min_(b ≠ 0)f(ab) for Rogers' refinement. Sekhon conjectures that widetilde(f) is ultra-Euclidean whenever f is, which would force every domain carrying an ultra-Euclidean function to be a field or a polynomial ring K[x]; that consequence was asked independently, and earlier, by Elliott on MathOverflow and by Elliott and Epstein, and under the extra hypothesis of submultiplicativity it is known. We prove that an ultra-Euclidean function makes every nonzero integer multiple of 1 a unit. Hence a characteristic-zero domain carrying one is a ℚ-algebra, and ℤ — although it is a Euclidean domain — carries no ultra-Euclidean function at all, as does no ring of integers of a number field; on all such rings the conjecture holds vacuously. In characteristic p>0 we prove the conjecture for every domain whose units are exactly the nonzero elements of the prime field, in the strong form that every ultra-Euclidean function there is already submultiplicative and equal to its own refinement; the case R=𝔽ₚ[x] is included. We also settle the conjecture on every field and exhibit an ultra-Euclidean function on ℚ that is not submultiplicative, which our first theorem shows is the smallest such example in characteristic zero. The results below are machine-checked in Lean 4, with the exceptions identified in S[sec:verif]; none of them rests on an exhaustive search or on compiled evaluation.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   ee6a745a33fd13831a94f203d3c2472908d38b6f98605aa50c8912ce3194c6a9