1
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.