[#P101192] Permutations whose index sums are always perfect squares

Problem. For which \(n\) does there exist a permutation \(\sigma\) of \(\{1, \dots, n\}\) such that \(i + \sigma(i)\) is a perfect square for every \(i\)? Is the set of exceptions exactly \(\{1, 2, 4, 6, 7, 11\}\), so that such a permutation exists for every \(n \ge 12\)?

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Problem setup

Definition 1. A permutation sigma of {1,...,n} is a bijection from that set to itself.

Remark 1. Equivalently, this asks for a perfect matching in the bipartite graph joining i on the left to j on the right whenever i+j is a perfect square.

2What counts as a solution

Prove that a suitable permutation exists for every n at least 12, or exhibit some n at least 12 for which none exists.

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (The six listed orders are the exact exception set). A square-sum permutation exists exactly when \(n\notin\{1,2,4,6,7,11\}\).^[1]

Resolution argument

Robert Israel gave a complete construction and obstruction argument in 2012. Suppose a working permutation is known on \([r]\). Choose a square \(q\) and set \(r=q-n-1\), with \(0\leq r<n\). Keep the permutation on \([r]\), and set \(\sigma(i)=q-i\) on \([r+1,n]\). The latter interval maps to itself and every new sum is \(q\).

Strong induction uses seven base witnesses at \(n=3,5,8,9,10,13,17\). For \(n\geq12\), the square immediately above \(n\), or the following square in the six exceptional remainder cases, reduces the order to an earlier admissible one.

Hall's theorem proves failure at the six exceptions. Deficient left sets are \(\{1\}\) for \(n=1,2\), \(\{4\}\) for \(n=4\), \(\{1,6\}\) for \(n=6,7\), and \(\{4,11\}\) for \(n=11\). Their neighbor sets have sizes \(0,0,0,1,1,1\), respectively. The candidate's proposed classification is therefore a solved theorem.

1Packet records

Show recorded summaries

Record	Kind	Assessment
A square-sum permutation exists exactly when \(n\notin\{1,2,4,6,7,11\}\).	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 1 A square-sum permutation exists exactly when \(n\notin\{1,2,4,6,7,11\}\).^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope every positive integer n Sources Reference 1 Argument Robert Israel gave a complete construction and obstruction argument in 2012. Suppose a working permutation is known on \([r]\). Choose a square \(q\) and set \(r=q-n-1\), with \(0\leq r<n\). Keep the permutation on \([r]\), and set \(\sigma(i)=q-i\) on \([r+1,n]\). The latter interval maps to itself and every new sum is \(q\). Strong induction uses seven base witnesses at \(n=3,5,8,9,10,13,17\). For \(n\geq12\), the square immediately above \(n\), or the following square in the six exceptional remainder cases, reduces the order to an earlier admissible one. Hall's theorem proves failure at the six exceptions. Deficient left sets are \(\{1\}\) for \(n=1,2\), \(\{4\}\) for \(n=4\), \(\{1,6\}\) for \(n=6,7\), and \(\{4,11\}\) for \(n=11\). Their neighbor sets have sizes \(0,0,0,1,1,1\), respectively. The candidate's proposed classification is therefore a solved theorem. Open full record →
For every \(m\geq0\), the set \(\{0,\ldots,m\}\) has a permutation whose termwise sums are squares.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 2 For every \(m\geq0\), the set \(\{0,\ldots,m\}\) has a permutation whose termwise sums are squares.^[2] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope every finite initial interval indexed from zero Sources Reference 2 Argument Benjamin Schwartz introduced square permutations in Mathematics Magazine and proved existence on every zero-based initial interval. The indexing changes the answer: the zero-based problem has no exceptional orders, while the one-based candidate has six. Both use the same reflection construction. This source also separates the entry from the square-sum sequencing puzzle, which asks for a Hamiltonian path rather than a bipartite perfect matching. Related: Proposition 1 Open full record →
Exact bipartite matching finds failures only at \(1,2,4,6,7,11\) through \(n=260\).	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Exact bipartite matching finds failures only at \(1,2,4,6,7,11\) through \(n=260\). Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope every positive integer n from 1 through 260 File research/candidate-screening/verify.py Details For each order, the checker joins left vertex \(i\) to right vertex \(j\) exactly when \(i+j\) is a perfect square, then searches for a perfect matching. It records the six exceptional orders and succeeds at every other order through 260. The sourced induction proves the unrestricted theorem. Related: Proposition 1 Open full record →
No records match these filters.

Notes and companion material

Screened alongside the cube and triangular analogues. The cube version behaves completely differently, succeeding for only 10 values of n up to 80, because cubes are far too sparse to supply enough edges.

Original intake status. Status not established. The related problem of arranging 1 through n in a row so that adjacent sums are squares is known and was resolved for large n, so the matching version may also be known; no search was performed.

No literature search was carried out.
Note the distinction from the well-known square-sum problem: that one asks for a Hamiltonian path in the graph where i ~ j iff i+j is square, whereas this asks only for a perfect matching, which is a weaker requirement and a different graph (bipartite, with i allowed to map to itself when 2i is square).

Recorded example 1. For n = 3 take sigma(1) = 3, sigma(2) = 2, sigma(3) = 1, giving sums 4, 4, 4.

Recorded example 2. For n = 11 no such permutation exists.

Computational notes

Bipartite perfect matching decided exactly for every n from 1 to 260. A permutation exists for every n in that range except 1, 2, 4, 6, 7 and 11.

How the 3 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemPermutations whose index sums are always perfect squares

All 2 recorded relations between these records and the problem

2See also

Density of losing positions in the subtract-a-triangular gamecombinatorics
Density of losing positions in the subtract-a-cube gamecombinatorics
Determinants of the disjoint-binary-support matrixcombinatorics

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Permutations whose index sums are always perfect squares.” TheoremDB. P101192. Problem statement; statement text SHA-256 a0ce9362b2e3c05eb5561296847fdb0d84c8b77046cad3bb59f4622f6713c63d. https://theoremdb.org/statement/?ref=P101192

BibTeX

@misc{theoremdb-problem-a0ce9362b2e3c05eb5561296847fdb0d84c8b77046cad3bb59f4622f6713c63d,
  title = {{Permutations whose index sums are always perfect squares}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 a0ce9362b2e3c05eb5561296847fdb0d84c8b77046cad3bb59f4622f6713c63d},
  url = {https://theoremdb.org/statement/?ref=P101192}
}

Plain text: Built Markdown snapshot

This problem includes 3 records joined by 2 typed links, sourced from mathoverflow.net^[1], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

2 entries have incomplete source metadata. Each affected row names the fields that still need editorial review.

Packet source. Robert Israel, MathOverflow answer 117234, 26 December 2012; construction, base permutations, and Hall obstructions. ↗forum · reference source · checked 2026-07-24Source metadata incomplete: publication-style citation.Source use: citation only.Source named by the research packet.
Benjamin L. Schwartz, Square Permutations, Mathematics Magazine 51 (1978), pages 64-66. ↗scholarly publication · reference sourceSource metadata incomplete: publication-style citation, relevance note.Source use: citation only.

Original question generated by an agent and settled computationally for n up to 260.

[#P101192] Permutations whose index sums are always perfect squares

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Problem setup

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status