On the size of residue class

Question

Let $n \in \mathbb{N}$ be a odd number. Let $S \subseteq \{1,3,5,7,...,n-2,n\}$ and $|S|$ is even number. Let $R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \pmod k\}$ where $0\leq i\leq k-1$.

$\textbf{Question:}$ What is the upper bound $N$ on $k$ such that $\forall S$ such that $|S|>0$ is even $\exists k \leq N \quad \exists i$ such that $|R_i^k|$ is odd number. One can see that $N \leq n+1$. What is best upper bound one can get? Is it possible to get $O(\sqrt{n})$ or $O(n^{1/3})$ or better.

Answer 1

Not a full answer, but intuition that the answer is probably $\tilde{O}(n^\frac12)$ and a proof that the answer is $\Omega(n^\frac12)$.

First we show that the answer is at least $\Omega(n^\frac12).$ For some notation, for $1 \le i \le n$ let $x_i = 0$ depending on whether $i \in S$ or not. Now, consider all $k \le \frac{1}{3} n^\frac12$ say, and the values $R_i^k$ for each of these. For each of the $R_i^k$ to be even they would have to satisfy linear equations over $\mathbb{F}_2$ of the form $$x_i + x_{i+k} + \dots + x_{i+jk} \equiv 0 \pmod{2}, $$ where $i+jk$ is the largest integer at most $n$ that is $i \pmod{k}.$ If we only consider $k \le \frac{1}{3}n^\frac12$, we have $< \frac{n}{2}$ total equations, hence they cannot force $x_1 = x_2 = \dots = x_n = 0$.

I don't have a proof of the other direction, but these equations feel mostly independent at least when $k$ is prime; which is why I expect an answer of $\tilde{O}(n^\frac12)$ to be correct. I'll keep thinking; this feels like it'll need analytic NT if it's possible.