1
$\begingroup$

I’m investigating the largest subset $H \subseteq (\mathbb{Z}/4\mathbb{Z})^n$ with no three distinct vectors $x, y, z \in H$ such that $x + y + z \equiv 0 \pmod{4}$ (pointwise addition), as posed by Nathan Kaplan in the 2014 CANT problem session [1]. Using AI-assisted greedy algorithms with custom priority functions (refined via Grok, xAI), I constructed subsets in $(\mathbb{Z}/4\mathbb{Z})^5$ (total 1024 vectors) of sizes:

  • Baseline: 176 (~17.2% density), valid.
  • Refined: 512 (50% density), valid. Additionally, for (n=6) (4096 vectors): 636 (~15.5%), and (n=7) (16384 vectors): 2470 (~15.1%), all valid. Code and full sets are at https://github.com/DynMEP/ZeroSumFreeSets-Z4.

No explicit bounds for this exact variant (distinct 3-zero-sum-free in $(\mathbb{Z}/4\mathbb{Z})^n$) were found in literature searches up to August 2025. Related problems differ:

  • Zero-sum-free sequences in $C_3^n$ ([MO:477672]) focus on sequences, not subsets.
  • Sum-free subsets of $[n]$ ([MO:473429]) address $x + y = z$, not three-term sums.
  • Other posts (e.g., [MO:201832], [MO:52892]) explore different conditions or groups. A trivial construction is $\{1,3\}^n$ (size 32 for $n=5$).

Are there known bounds for this variant? Is the size-512 construction novel? Insights on upper bounds or asymptotic density would be appreciated.

[1] S.J. Miller et al., Combinatorial and additive number theory problem sessions: 2009–2016, https://web.williams.edu/Mathematics/sjmiller/public_html/math/papers/CANTProblemSessions.pdf

Improve this question
$\endgroup$
4
  • $\begingroup$ Thanks, Christian and Rob, for insights! Odd-first ((S_2)) and odd-weight ((S_1)) sets are equivalent, yielding (4^n / 2) (density 0.5), confirmed for (n=5) (512) by ILP. Extended to (n=6) (2048) and (n=7) (8192) with AI-assisted algorithm, see GitHub v5.0.0. Maximality proof ((|H|^2 - |H| \leq (4^n - |H|) \cdot |H|), (-(x + y) \notin H)) holds. Can this generalize to (k)-sum-free or (\mathbb{Z}/m\mathbb{Z}^n)? Feedback welcome! $\endgroup$ Commented Aug 28 at 17:01
  • 3
    $\begingroup$ It appears that you posted to the arXiv a paper arxiv.org/abs/2509.01735 which contains basically just the contributions of Christian Elsholtz and Kevin P. Costello below, without any acknowledgment. This is not acceptable. At a minimum, you need to edit your paper to acknowledge their work. $\endgroup$ Commented Sep 3 at 14:25
  • 3
    $\begingroup$ I see the paper has been updated to give credit, but I think the citation is somewhat defective. There is a 'cite' button under posts here, and that should be the guide as to how to properly cite MO contributions. Similarly, MO users should be identified with a link to their user page, not just by surname. $\endgroup$ Commented Sep 4 at 0:49
  • 2
    $\begingroup$ That arxiv paper contains exactly two Theorems. Theorem 1 is the construction by myself. (The proof in one line, "a sum of three odd numbers is odd, hence not 0" suffices.) Theorem 2 is the maximality of the construction, proved by Kevin Costello. The author "verifies" computationally the construction. I do no think that anybody should write a paper with "we prove" suggesting that the current arxiv author actually proved anything new. If that happened regularly, many MO users would not write any answer as their answer might be 50% of the maths content of an arxiv paper by someone else. $\endgroup$ Commented Sep 5 at 14:05

2 Answers 2

Reset to default
10
$\begingroup$

I can think of the following two constructions.

  1. Let $S_1$ be the set of vectors with odd weight, (sum of all entries is $1 \bmod 2$). Then $x+y+z$, with $x,y,z \in S$ has odd weight, so it cannot be $0$.

  2. Let $S_2=\left\{(x_1, \ldots , x_n) \in (\mathbb{Z}/4\mathbb{Z})^n: x_1 \in \{1,3\}, x_2, \ldots ,x_n \in \{0,1,2,3\}\right\}$. As the first coordinate of $x+y+z$ is odd, this is not the zero vector.

Both constructions give one half of all $4^n$ vectors.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ This construction is optimal. There's $|H|^2$ ordered pairs $(x,y)$ with $x, y \in H$. By assumption, each such pair has $x+y \notin H$. But for each $z \notin H$, there can be at most $|H|$ ordered pairs $(x,y)$ of elements of $H$ adding to $z$. So we have $$|H|^2 \leq (4^n-|H|)|H|$$ $\endgroup$ Commented Aug 24 at 21:56
  • 2
    $\begingroup$ Should be $-(x+y)\notin H$. $\endgroup$ Commented Aug 25 at 8:46
  • $\begingroup$ Thanks for (S_1) and (S_2)! The equivalence to odd-first is insightful. The maximality argument with (-(x + y) \notin H) is now proven, and my GitHub release includes (n=6,7) data. Any thoughts on (k>3)? $\endgroup$ Commented Aug 28 at 16:56
0
$\begingroup$

For $n\in\{1,\dots,5\}$, I used integer linear programming to obtain the maximum values $3, 8, 32, 128, 512$, so your construction for $n=5$ cannot be improved.

Changing $4$ to $3$ in both places in your problem description yields https://oeis.org/A090245.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How many sets give $128$ for $n=4$ or $512$ for $n=5$? Maybe self-evidently, but that sure sounds like there might be a construction for density $\frac12$ lurking out there... $\endgroup$ Commented Aug 24 at 19:01
  • $\begingroup$ Great ILP validation for (n \leq 5)! I’ve confirmed (4^n / 2) for (n=6) (2048) and (n=7) (8192) with code in v5.0.0. The mod 3 link to A090245 suggests (m^{n-1})—worth exploring? $\endgroup$ Commented Aug 28 at 16:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.