Simplify in GF(2)

I have computations that I perform symbolically, but they involve integers modulo 2.

It seems that Matlab does not simplify mod expressions (e.g., mod(sym('x')+2,2) results in mod(x + 2, 2) ; specifying that x is an integer does not change anything). Even assuming my variables are integers between 0 and 1 does not result in simpler expressions. For instance:

syms x;
assume(in(x,"integer") & (x>=0) & (x<=1));
simplify(x*x)
% ans = x^2
% I would expect ans = x

In my expressions where I only work in GF(2) using polynomial expressions recursively on matrices of symbols, I rapidly obtain gigantic expressions that would be trivially simplified (e.g: 2*x^8*y*z + x*y^2 + x^2*y etc. that would here be 0, but my formulas are way longer and I can't do it by hand).

Is-there any way to make Matlab simplify expressions knowing that they involve computations modulo 2 ? I use R2023b.

Thanks !

Answer 1

[John D'Errico]

In the help docs for simplify, we see:

"S = simplify(expr) performs algebraic simplification of expr."

The key word there is ALGEBRAIC.

However, you want it to perform simplification in mod 2 arithmetic. Simplify is not designed to solve that problem. In order for MATLAB to perform what you wish to see, this would require it to evaluate the equivalent of truth tables, over possibly many variables.

Now, could you make that expression simpler?

syms x y z
expr = 2*x^8*y*z + x*y^2 + x^2*y

Knowing that x and x^n are the same for a binary variable x, you could do this:

expr = subs(expr,[x^2 y^2],[x y])

And you could do it again, until you come to something simpler, that you could simplify. But just wanting code to do what it is not designed to do will never work.

[Nicolas]

Thanks! I had assumed that at least having assume(in(x,"integer") & (x>=0) & (x<=1)); would help simplify, otherwise I am not sure how this is useful to have these assumptions.

Given you suggestion and with some chatgpt, I attached a simplifymod2() function that seems to do the job. Thanks again !

[Nicolas]

oh, important bug spotted : if there is a number in a variable name, it gets simplified too ;)