  For a polynomial progression $$(x, x+P_1(y), ..., x+P_{t}(y)),$$ we define
four notions of complexity: Host-Kra complexity, Weyl complexity, true
complexity and algebraic complexity. The first two describe the smallest
characteristic factor of the progression, the third one refers to the
smallest-degree Gowers norm controlling the progression, and the fourth one
concerns algebraic relations between terms of the progressions. We conjecture
that these four notions are equivalent, which would give a purely algebraic
criterion for determining the smallest Host-Kra factor or the smallest Gowers
norm controlling a given progression. We prove this conjecture for all
progressions whose terms only satisfy homogeneous algebraic relations and
linear combinations thereof. This family of polynomial progressions includes,
but is not limited to, arithmetic progressions, progressions with linearly
independent polynomials $P_1, ..., P_t$ and progressions whose terms satisfy no
quadratic relations. For progressions that satisfy only linear relations, such
as $$(x, x+y^2, x+2y^2, x+y^3, x+2y^3),$$ we derive several combinatorial and
dynamical corollaries: (1) an estimate for the count of such progressions in
subsets of cyclic groups or totally ergodic dynamical systems; (2) a lower
bound for multiple recurrence; (3) and a popular common difference result in
cyclic groups. Lastly, we show that Weyl complexity and algebraic complexity
always agree, which gives a straightforward algebraic description of Weyl
complexity.
