Constructing strong starters of orders $3p$: triplication with SAT solver
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910044379938816 |
|---|---|
| author | Ogandzhanyants, Oleg Sadov, Sergey Kondratieva, Margo |
| author_facet | Ogandzhanyants, Oleg Sadov, Sergey Kondratieva, Margo |
| contents | A novel approach to building strong starters in cyclic groups of orders $n$ divisible by 3 from starters of smaller orders is presented. A strong starter in $Z_n$ ($n$ odd) is a partition of the set $\{1,2,\dots,n-1\}$ into pairs $\{a_i,b_i\}$ such that all pair sums $a_i+b_i$ are distinct and nonzero modulo $n$ and all differences $\pm(a_i-b_i)$ are distinct and nonzero modulo $n$. A special interest to strong starters of odd orders divisible by 3 is motivated by Horton's conjecture which claims that such starters exist (except when $n=3$ or $9$) but remains unproven since 1989.
We begin with a strong starter of order $p$ coprime with 3 and describe an algorithm to obtain a Sudoku-type problem modulo 3 whose solution, if exists, yields a strong starter of order $3p$. The process leading from the original to the final starter is called {\em triplication}.
Besides theoretical aspects of the construction, practicality of this approach is demonstrated. A general-purpose constraint-satisfaction (SAT) solver z3 is used to solve the Sudoku-type problem; various performance statistics are presented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06461 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constructing strong starters of orders $3p$: triplication with SAT solver Ogandzhanyants, Oleg Sadov, Sergey Kondratieva, Margo Combinatorics 05B05 G.2.1 A novel approach to building strong starters in cyclic groups of orders $n$ divisible by 3 from starters of smaller orders is presented. A strong starter in $Z_n$ ($n$ odd) is a partition of the set $\{1,2,\dots,n-1\}$ into pairs $\{a_i,b_i\}$ such that all pair sums $a_i+b_i$ are distinct and nonzero modulo $n$ and all differences $\pm(a_i-b_i)$ are distinct and nonzero modulo $n$. A special interest to strong starters of odd orders divisible by 3 is motivated by Horton's conjecture which claims that such starters exist (except when $n=3$ or $9$) but remains unproven since 1989. We begin with a strong starter of order $p$ coprime with 3 and describe an algorithm to obtain a Sudoku-type problem modulo 3 whose solution, if exists, yields a strong starter of order $3p$. The process leading from the original to the final starter is called {\em triplication}. Besides theoretical aspects of the construction, practicality of this approach is demonstrated. A general-purpose constraint-satisfaction (SAT) solver z3 is used to solve the Sudoku-type problem; various performance statistics are presented. |
| title | Constructing strong starters of orders $3p$: triplication with SAT solver |
| topic | Combinatorics 05B05 G.2.1 |
| url | https://arxiv.org/abs/2506.06461 |