The triplication method for constructing strong starters

Imagine you are trying to build a massive, perfect jigsaw puzzle. The puzzle represents a complex mathematical structure called a Strong Starter. These structures are like secret codes used in cryptography, scheduling tournaments, and designing communication networks.

The problem is: building these puzzles from scratch is incredibly hard, especially when the puzzle size is a multiple of 3 (like 21, 27, or 45 pieces).

This paper introduces a clever new construction technique called the "Triplication Method." Think of it as a magic recipe that lets you build a giant puzzle (size $3m $) by starting with a much smaller, simpler puzzle (size$ m$) and then "triplicating" it.

Here is the breakdown of their breakthrough, explained through simple analogies:

1. The Old Problem: The "No-Go" Zone

Previously, the authors had a recipe that worked great, but it had a strict rule: You could only use it if the small puzzle size ( $m$ ) wasn't divisible by 3.

Analogy: Imagine you have a recipe for making a triple-layer cake. It worked perfectly if your base layer was 7 inches wide. But if you tried to use a 9-inch base layer (because 9 is divisible by 3), the recipe would fail, and the cake would collapse. This limited the types of cakes (or mathematical structures) you could bake.

2. The New Magic: The "Triplication Table"

The authors realized that to build the big puzzle, you don't just need the small puzzle; you need a Blueprint (which they call a Triplication Table).

The Blueprint: Imagine taking your small puzzle and laying it out on a grid with 3 columns.
- Column 1 is the original small puzzle.
- Column 2 is a slightly shifted version of the puzzle.
- Column 3 is another shifted version.
The Twist: In the old method, these columns had to be perfect copies of a specific type of puzzle. In this new paper, the authors say: "Hey, we can be more flexible!" You can now use "Pseudostarters" (almost-puzzles) or mix and match three different puzzles to create the blueprint. This is like realizing you can build the cake base using flour, or a mix of flour and almond meal, as long as the proportions are right.

3. The "Sudoku" Step

Once you have your Blueprint (the Triplication Table), you don't just copy-paste it. You have to solve a Sudoku-like puzzle.

The Analogy: Imagine your Blueprint is a grid of empty boxes. You need to fill these boxes with numbers (0, 1, 2) following specific rules so that no two numbers clash in a way that breaks the final structure.
The Innovation: The authors realized there are two different ways to play this Sudoku game:
1. The "Mod" Scenario: This is the old way. It's like solving Sudoku on a circular clock face. It works well, but it gets mathematically messy if your base size is divisible by 3.
2. The "Carry" Scenario: This is the new superpower. It's like solving Sudoku on a standard number line where you just count up and carry over (like adding 9 + 1 = 10).
- Why it matters: The "Carry" method is so simple and robust that it ignores the old rule. It works whether your base size is 7, 9, 15, or 21. It's like finding a universal key that opens every door, regardless of the lock type.

4. The Final Assembly: Chinese Remainder Theorem (The Glue)

Once you have your Blueprint and you've solved the Sudoku (found the right numbers to fill the gaps), you combine them.

The Analogy: You have the "shape" of the pieces (from the small puzzle) and the "color code" (from the Sudoku). You use a mathematical glue called the Chinese Remainder Theorem to snap them together.
The Result: You pop out a brand new, giant Strong Starter (size $3m$) that is mathematically perfect.

Summary of the Breakthrough

Before: You could only build big structures if the small one was "clean" (not divisible by 3).
Now: By generalizing the Blueprint and inventing the "Carry" Sudoku method, you can build any strong structure of size $3m$, even if the small one is messy or divisible by 3.

In a nutshell: The authors took a rigid, finicky construction kit and turned it into a flexible, universal toolkit. They showed that by changing how you "encode" the numbers (using a simple "carry" system instead of a complex modular one), you can unlock the ability to build mathematical structures that were previously thought impossible to construct this way.

They even tested this on computers, and it worked like a charm, generating thousands of new, valid structures that mathematicians can now use for their own secret codes and designs.

Here is a detailed technical summary of the paper "The triplication method for constructing strong starters."

1. Problem Statement

The paper addresses the construction of strong starters in cyclic groups of order $n = 3m$ , where $m$ is an odd integer.

Strong Starters: A strong starter in $\mathbb{Z}_n$ $Z_{n}$ is a partition of the non-zero elements $\mathbb{Z}_n^*$ $Z_{n}^{*}$ into $k = (n-1)/2$ $k = (n - 1) /2$ pairs $\{(x_i, y_i)\}$ ${(x_{i}, y_{i})}$ such that:
1. The set of differences $\{\pm(x_i - y_i)\}$ covers $\mathbb{Z}_n^*$ .
2. The set of sums $\{x_i + y_i\}$ contains no zero and has distinct non-zero values.
The Challenge: Previous work by the authors (2025) introduced a "triplication method" to construct strong starters of order $3m $from starters of order$ m $. However, that method was limited to cases where$ m$ is not divisible by 3.
Goal: To generalize the triplication method to eliminate the restriction that $m$ must be coprime to 3, thereby allowing the construction of strong starters for any odd order $n = 3m$ .

2. Methodology

The authors develop a generalized framework that reduces the construction of a strong starter to solving a Modular Sudoku Problem (MSP). The process involves three main stages:

A. Generalization of the Triplication Table (TT)

The core object is the Triplication Table ( $\Sigma_m$ ), a dataset derived from a strong starter of order $3m $reduced modulo$ m$.

Structure: A table with $q+1$ $q + 1$ rows and 3 columns (where $m=2q+1$ $m = 2 q + 1$ ).
- Special Row (Row 0): Contains a single pair $(t, t)$ called the "key."
- Regular Rows (Rows 1 to $q$ ): Contain three pairs each, where the directed differences of the pairs in row $i$ are all equal to $\pm i \pmod m$ .
New Definition: The paper generalizes the construction of $\Sigma_m$ $Σ_{m}$ . Previously, it was built from a single starter. The new definition allows $\Sigma_m$ $Σ_{m}$ to be constructed from:
1. One starter (using a starter and its conjugate).
2. Three distinct starters.
3. Pseudostarters: Specifically, "balanced triples" of pseudostarters (where elements may repeat or be missing, provided specific multiplicity conditions are met).
4. Epicycloidal Pseudostarters: A specific geometric construction based on multipliers $\mu$ .

B. Discrimination Scenarios and Modular Sudoku

To recover the original strong starter of order $3m $from$ \Sigma_m $, one must determine the "discriminators" (the quotient part of the number when divided by$ m $). The authors introduce two scenarios for encoding numbers$ x \in \mathbb{Z}_{3m} $as pairs$ (u, U) $where$ u = x \pmod m $and$ U$ is a discriminator:

Mod Scenario (Modular Discrimination):
- Applicable when $m = 3^\nu p$ ( $\nu \ge 0, 3 \nmid p$ ).
- Discriminator $U = x \pmod{3^{\nu+1}}$ .
- The MSP is solved modulo $r = 3^{\nu+1}$ .
- Recovery uses an extended Chinese Remainder Theorem (CRT) handling non-coprime moduli.
Carry Scenario (Quotient Discrimination):
- Applicable regardless of whether $m$ is divisible by 3.
- Discriminator $U = \lfloor x/m \rfloor \in \{0, 1, 2\}$ .
- The MSP is solved modulo $r = 3$ .
- Key Innovation: Instead of CRT, recovery uses simple arithmetic: $x = mU + u$ .
- Operations: The arithmetic operations in the Sudoku problem ( $\oplus, \ominus$ ) are modified to account for "carries" when $u_1 + u_2 \ge m$ or $u_1 - u_2 < 0$ .

C. The Modular Sudoku Problem (MSP)

Given a Triplication Table $\Sigma_m$ , the MSP seeks a table $\tilde{\Sigma}_r$ (the discriminators) satisfying specific constraints:

Row Constraints: Differences of discriminators in regular rows must be distinct.
Weak Set Constraints: Sums of discriminators for pairs with the same sum modulo $m$ must be distinct.
Color Constraints: Discriminators for pairs sharing the same value modulo $m$ must be distinct.
Consistency Constraints: The pair $(u, U)$ must be valid within the chosen discrimination scenario.

3. Key Contributions

Removal of the "Not Divisible by 3" Restriction: The paper proves that strong starters of order $3m $can be constructed for **any** odd$ m$, including those divisible by 3, by utilizing the Carry Scenario.
Generalized Triplication Table Definition: The definition of $\Sigma_m$ is expanded to include constructions based on three starters or pseudostarters (including epicycloidal types), significantly broadening the pool of base materials for construction.
Theoretical Unification: The authors prove Theorem 3.9, demonstrating that the set of strong starters obtainable from a given Triplication Table is independent of the discrimination scenario (Mod vs. Carry). Both scenarios yield the same set of solutions if a solution to the MSP exists.
Explicit Recovery Algorithms:
- Provided explicit formulas for recovering $x$ in the Mod scenario (handling non-coprime moduli).
- Provided explicit formulas for the Carry scenario using simple quotient/remainder arithmetic.

4. Results

Solvability: The authors implemented the method in Python using the SAT solver z3.
- Empirical Evidence: For Triplication Tables constructed via the specific templates (Section 4), the MSP is almost always solvable.
- Conjecture 7.1: If a Triplication Table is constructed from a valid template (using starters/pseudostarters), a solution to the MSP exists.
- Counter-examples: The paper identifies that for randomly generated Triplication Tables (not following specific templates), the MSP may be unsolvable. However, such "bad" tables are rare in random sampling (e.g., only 27 out of 4000 for $m=9$ ).
Examples: The paper provides concrete constructions of strong starters for orders 21, 27, 45, and others, including cases where $m$ is a multiple of 3 (e.g., $m=9, 15$ ).

5. Significance

Combinatorial Design: This work significantly expands the known universe of strong starters, which are fundamental in constructing Room Squares, Howell designs, and other combinatorial structures.
Algorithmic Efficiency: The "Carry" scenario offers a computationally cheaper alternative to the Mod scenario (solving modulo 3 vs. modulo $3^{\nu+1}$) and simplifies the final reconstruction step (no CRT required).
Theoretical Insight: By decoupling the construction of the Triplication Table from the specific discrimination scenario, the authors provide a more robust theoretical understanding of the relationship between starters of order $m$ and $3m$.
Practical Application: The method is fully algorithmic and programmable, allowing for the automated generation of large strong starters that were previously inaccessible due to the divisibility constraints of $m$ .

In summary, the paper transforms the triplication method from a specialized tool for coprime orders into a universal construction technique for strong starters of any odd order divisible by 3, leveraging generalized table definitions and a novel "Carry" discrimination scenario.