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.