Let $f : \{1,2\}^n \rightarrow \mathbb{Z}_3$ be a function from the multiplicative subgroup of order $2$ of $\mathbb{Z}_3$ over $n$ variables ($\{1,2\}^n$) to $\mathbb{Z}_3$, such that each coordinate is chosen uniformly at random.
Can we bound the probability that $f$ has $m$ monomials in the polynomial $p(x)$ represents it (the one with the lowest degree,I assume $p(x)$ was obtained by interpretation process )?
My intuition tells me this number has to be roughly $2^n$ (i.e. all the monomials appear), but I struggle saying something quantitative.
Unless I misunderstood the question is about representing functions from the set $$S=\{1,2\}^n\subset\Bbb{Z}_3^n$$ to $\Bbb{Z}_3$ as polynomials in $R_n:=\Bbb{Z}_3[x_1,x_2,\ldots,x_n]$. It is well known and easy to see that to any function $f:\Bbb{Z}_3^n\to\Bbb{Z}_3$ there exists a polynomial $P\in R_n$ such that $P(a_1,a_2,\ldots,a_n)=f(a_1,a_2,\ldots,a_n)$ for all $(a_1,a_2,\ldots,a_n)\in\Bbb{Z}_3^n$. It follows that the same applies to functions $f:S\to \Bbb{Z}_3$ (extend $f$ outside of $S$ any which way you want, and you still find a matching polynomial $P$).
On the set $S$ the polynomials $x_i^2-1$ give rise to the zero function, so if $$I(S)=\langle x_i^2-1\mid i=1,2,\ldots,n\rangle_{R_n}\subset R_n$$ is the ideal they generate, then we can replace $P$ with the lowest degree element in its coset $P+I$ without changing the function $f:S\to\Bbb{Z}_3$. Using the congruences $x_i^2\equiv1\pmod I$ we can thus find a polynomial $P'\in P+I$ such that $P'$ is in the $\Bbb{Z}_3$-span $D$ of $$ D=\langle \prod_{j\in J}x_j\mid J\subseteq \{1,2,\ldots,n\}\rangle_{\Bbb{Z}_3} $$ all the $2^n$ products $x_J:=\prod_{j\in J}x_j$ of distinct variables $x_j$.
The space of functions $F(S):=\{f:S\to\Bbb{Z}_3\}$ also has dimension $|S|=2^n$, so to each function $f\in F(S)$ we can associate a unique polynomial $P\in D$.
After this longish setting up of the scene the question can be formulated unambíguously and answered easily! Namely, the question is what is the expected number of terms $x_J, J\subseteq \{1,2,\ldots,n\}$ in a uniformly chosen random element of $D$?
The answer follows from the observation that the term $x_J$ appears in the sum $\sum_{J}a_Jx_J$ if and only if the coefficient $a_J$ is non-zero. Because the choice of $a_J$ is uniform over $\Bbb{Z}_3$, this happens with probability $2/3$.