# Modelling L-0 norm of a vector

I have a binary variable $$\bf x$$ of length 4000. Let $${\bf x}=[x_1,x_2,\cdots, x_{4000}]$$.

Let's say we have $${\bf y}=[y_1,y_2,y_3,y_4]$$, where \begin{align} y_1&=x_1+x_5+x_{9}+\cdots+x_{3997} \\ y_2&=x_2+x_{6}+x_{10}+\cdots+x_{3998} \\ y_3&=x_3+x_{7}+x_{11}+\cdots+x_{3999} \\ y_4&=x_4+x_{8}+x_{12}+\cdots+x_{4000} \end{align}

Now, the constraint I have is: the number of nonzero elements in $${\bf y}$$ is $$\le 2$$

In other words, the $$l_0$$ norm of vector $${\bf y}$$ is $$\le 2$$

How to model this constraint with and without (if possible) introducing new variables?

With new variables $$z_i$$

$$y_i \leq M \cdot z_i \quad \text{for } i = 1, 2, 3, 4$$

$$\sum_{i=1}^{4} z_i \leq 2$$

Is it correct? If yes, what would be a good value for $$M$$?

Yes, this is correct and is the standard approach. You want $$M$$ to be a small upper bound on the left hand side when $$z_i=1$$, so take $$M$$ to be the number of $$x$$ variables on the right hand side of the equality constraint for $$y_i$$. In your example, that would be $$M=1000$$.
If $$y$$ does not appear anywhere else in your model, you can eliminate it by substitution, yielding constraints of the form $$\sum_j x_j \le M z_i$$, which you can optionally strengthen by disaggregating to $$x_j \le z_i$$. The resulting formulation is essentially the same as in https://or.stackexchange.com/a/11785/500