Let $\mathcal{L}=\{0,S,+,\cdot,=,<,X,R,S\}$ be the language of arithmetic with three additional predicate symbols $X(v)$, $R(v,u)$ and $S(v,u)$.


Let $\phi(x),\psi(x,y)$ and $\eta(x,y)$ be formulas in $\mathcal{L}$. Define the formula $\Theta\_e(\phi,\psi,\eta)$ in $\mathcal{L}$ for some $e\in \mathbb{N}$ which says:


1. $\phi(0)$
2. $\psi$ is a partition of $\{x:\phi(x)\}$ into classes of size $e$.
3. $\eta$ is a partition of $\{x:\phi(x)\land \neg x=0\}$ into classes of size $e$.



> 
> **Theorem**. For every fix prime number $p,q\in \mathbb{N}$, ${\bf I}\Delta\_0(R,S,X)+\Theta\_p(R,S,X)+\{\neg \Theta\_q(R',S',X'):R',S',X'\in \Delta\_0(R,S,X)\}\not \vdash \bot$
> 
> 
> 


Proof. One of the proofs of this theorem can be found [here](http://www.karlin.mff.cuni.cz/~krajicek/ens.ps).



> 
> Q1. Is there any similar result for counting modulo a composite number? For example is ${\bf I}\Delta\_0(R,S,X)+\Theta\_7(R,S,X)+\{\neg \Theta\_6(R',S',X'):R',S',X'\in \Delta\_0(R,S,X)\}$ consistent?
> 
> 
> Q2. Suppose that the theory above is consistent. Does it imply separation of complexity classes like $AC\_0[6]$ and $NP$?
> 
> 
> 


Thanks in advance.



Bounded Arithmetic and Counting
Q1: Yes. The paper you linked to in the question actually proves the theorem for every pair of natural numbers $p,q$ such that $p$ has a prime factor that does not divide $q$ (in other words, $p$ does not divide any power of $q$).


Q2: No. Even at the best of times, you'd only get the conclusion that the classes are different *in some model of the theory*, not necessarily the standard model. However, the theory here is too weak even for that. Passing to the second-order language as used e.g. by Cook and Nguyen, you'd need to prove separation from the theory $V^0(6)$ to make things work. Your schema consists of instances of the $\forall\Sigma^B\_0$ mod-6 counting axiom, which is weaker than the $\forall\Sigma^B\_1$ axiom of $V^0(6)$ asserting the *existence* of suitable mod-6 counting functions.


