Given a natural number $ n \geq 1$ , I am looking for a Boolean circuit over $ 2n$ variables, $ \varphi(x_1, y_1, \dots, x_n, y_n)$ , such that the output is true if and only if the assignment that makes it true verifies

$ $ \sum_{i = 1}^{i = n} (x_i + y_i) \not\equiv n \bmod 3$ $

I should specify that this I am looking for a Boolean *circuit*, not necessarily a Boolean formula as it is usually written in Conjunctive Normal Form (CNF). This is because when written in CNF, a formula like the one before has a trivial representation where the number of clauses is approximately $ \frac{4^n}{3}$ , as it contains a clause for every assignment $ (x_1, y_1, \dots, x_n, y_n)$ whose bits sum to a value which is congruent with $ n \bmod 3$ . Constructing such a formula would therefore take exponential time.

I have been told that a Boolean circuit can be found for this formula that accepts a representation of size polynomial in $ n$ . However, so far I have been unable to find it. I would use some help; thanks.