MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to construct examples (describe all) polynoms f,g such that for any polynom p(x) not equal to zero: |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms (=Hamming weight, by the way it is norm on the polynomial algebra).

I am mainly interested in the case of polynoms over F_2.

The difficulty is that if we take just one polynom f(x) we can find p(x) such that fp=x^N-1 (see answer to this quest) so |fp|=2 - small. But if we take 2 this trick will not work.

I think that random polynoms will satisfy this property.

Example of such polynoms is given here Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

Same argument also works for f = x^n+1; g = x^n +x^k+1.

A bit modification allows to prove for f=x^n+x^l+1; g=x^n+x^k+1.

Here is example which violate this property:

f= x^N + x^3 + x^2+x+1; g=x^N + x^4 + x^3 + x^2+x+1 , N>=6

p(x)=x+1 will give contradiction.

Such polynoms generate "good" convolutional codes. See Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)

The same can be asked about triples and n-tuples of polynoms.

By the way is the any easy way to see that polynoms:

% The octal representation of the polynomials are

G4 = 133; % 1+D^2+D^3+D^5+D^6

G7 = 171; % 1+D+D^2+D^3+D^6

G5 = 145; % 1+D+D^4+D^6

Satisfy this property ? These polynoms used in some part of GSM.

From MatLab demo file:

%% EGPRS2 Background

% The 3GPP standard introduced General Packet Radio Service (GPRS) to

% support packet switched wireless data transmission over GSM networks.

% The Enhanced GPRS (EGPRS Phase 1) specifications increased the data rates

% by using 8-PSK modulation. In 2007, with the introduction of EGPRS Phase

% 2 (EGPRS2) even higher data rates are achieved through the use of higher

% modulation schemes such as 16- and 32-QAM. EGPRS2 Level B also

% introduced an increased symbol rate of 325 kSps as opposed to the legacy

% symbol rate of 270,833 kSps [ <#25 2> ]. In this demo, we focus on the

% UBS-7 channel, which provides 44.8 kbps data rate [ <#25 4> ]. We assume

% that PAN [ <#25 4> ] is not included in the data. Some key system

% parameters are as follows [ <#25 2>, <#25 4> ]:

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.