MATH.11:4.2 - Choose a small expression family

Look at what the transformations add, remove or combine. For states represented by counts x1,…,xn, try a weighted total:

I(x)=w1*x1+...+wn*xn.

The unknown weights let different kinds contribute differently. For additive changes x → x+d, the change in that total is w1*d1+...+wn*dn.

If the update combines variables or changes an accumulated sum, try a few expressions suggested by those operations. For example, an update containing n can make n² useful because (n+1)^2-n^2=2*n+1. Write a candidate as I(x)=c1*p1(x)+...+ck*pk(x), where the expressions pi are chosen and the coefficients ci are unknown.

A known invariant, a calculated short sequence or an equation needed at the target can suggest these expressions. Choose only as large a family as the next question warrants. A larger polynomial degree adds unknowns and substitution work.

Choose the value arithmetic too. If the question concerns a remainder, calculate the proposed invariant modulo the relevant integer. That can preserve a distinction which an ordinary rational-valued linear expression misses.