# leenorm.kash
# KASH 2.x code accompanying the paper "Exact values of the Waring function
# for selected finite fields: the combinatorics" by Christiaan van de Woestijne
# KASH: http://www.math.TU-Berlin.de/~kant/kash.html
# Note: this code is written in KASH 2.5 and probably will not run under KASH 3
# Written by: Christiaan van de Woestijne, December 2006 - February 2007
# Author email: c.vandewoestijne@tugraz.at
# AVAILABLE FUNCTIONS IN THIS FILE
# LeeAbsoluteValue := function( a, m )
# m is a positive integer, a is an integer
# Computes the Lee absolute value: a mod m or m-(a mod m) depending on
# whether a mod m is larger or smaller than m/2
# LeeNorm := function( l, m )
# l is a list of integers, m is a positive integer
# Returns the Lee norm of the vector l
# AllOneVector := function( r )
# r is a nonnegative integer
# Returns a list of length r and all components equal to 1
# ModularVectorSum := function( v1, v2, m )
# v1 and v2 are lists of integers of equal length, m is a positive integer
# Computes the sum of v1 and v2 modulo m
# OrbitLeeNorm := function( l, m )
# l is a list of integers, m is a positive integer
# Returns the list of Lee norms of the vectors l+x*e, all components modulo
# m, where x runs over Z/mZ and e is the all-one vector
# IsAdmissible := function( l, m )
# l is a list of integers, m is a positive integer
# Tests whether l has the smallest Lee norm in its orbit under the action
# of the all-one vector
# NormBound := function( r, m )
# r and m are positive integers
# Maximal Lee norm of an admissible vector of length r over Z/mZ
# AdmissibleVector := function( m, r )
# m and r are positive integers
# Computes an admissible vector of length r and modulus m of maximal norm.
# Here "norm" means Lee norm and "maximal" is as given by the NormBound
# function.
# END OF DOCUMENTATION
##########################################################################
LeeAbsoluteValue := function( a, m )
# m is a positive integer, a is an integer
# Computes the Lee absolute value: a mod m or m-(a mod m) depending on
# whether a mod m is larger or smaller than m/2
if 2*(a mod m) > m then
return( m - (a mod m ) );
else
return( a mod m );
fi;
end;
LeeNorm := function( l, m )
# l is a list of integers, m is a positive integer
# Returns the Lee norm of the vector l
return Sum( List( l, i->LeeAbsoluteValue( i, m ) ) );
end;
AllOneVector := function( r )
# r is a nonnegative integer
# Returns a list of length r and all components equal to 1
return List( [1..r], i->1 );
end;
ModularVectorSum := function( v1, v2, m )
# v1 and v2 are lists of integers of equal length, m is a positive integer
# Computes the sum of v1 and v2 modulo m
return List( v1+v2, i->i mod m );
end;
OrbitLeeNorm := function( l, m )
# l is a list of integers, m is a positive integer
# Returns the list of Lee norms of the vectors l+x*e, all components modulo
# m, where x runs over Z/mZ and e is the all-one vector
local ee;
ee := AllOneVector( Length( l ) );
return List( [0..m-1], i->
LeeNorm( ModularVectorSum( l, i*ee, m ), m ) );
end;
IsAdmissible := function( l, m )
# l is a list of integers, m is a positive integer
# Tests whether l has the smallest Lee norm in its orbit under the action
# of the all-one vector
return Minimum( OrbitLeeNorm( l, m ) ) = LeeNorm( l, m );
end;
NormBound := function( r, m )
# r and m are positive integers
# Maximal Lee norm of an admissible vector of length r over Z/mZ
if m mod 2 = 0 and r mod 2 = 0 then
return m*r/4;
else
if r >= m then
if m mod 2 = 0 then # so r mod 2 = 1
return Floor( m*r/4 - 1/2 );
else # so m mod 2 = 1
return Floor( m*r/4 - r/(4*m) );
fi;
else # so r < m
if r mod 2 = 1 then
return Floor( m*r/4 - m/(4*r) );
else # so m mod 2 = 1 and r mod 2 = 0
return Floor( m*r/4 - r/(4*m) );
fi;
fi;
fi;
end;
# The following four functions are not meant to be called by the user.
# No input checking is done and comments are scarce.
# In all four, m is an integer modulus >= 1 and r is the dimension.
# Vectors are (mathematically) elements of (Z/mZ)^r, but their KASH
# appearance is simply as a list of integers between 0 and m-1 of length r.
AdmEvenEven := function( m, r )
# m and r are even
# returns an admissible vector of maximal norm
return Concatenation( List( [1..r/2], i->0 ), List( [1..r/2], i->m/2 ) );
end;
AdmOddEven := function( m, r )
# m is odd, r is even
# returns an admissible vector of maximal norm
local y, i, lst;
lst := [];
y := 0;
for i in [1..r/2] do
Append( lst, [y,(y+(m-1)/2) mod m] );
y := (y - (m-1)/2) mod m;
od;
return lst;
end;
AdmEvenOdd := function( m, r )
# m is even, r is odd, r <= 2m
local Q,R,i,lst,dinges;
Q := IntQuo( m/2, r );
R := m/2 mod r;
# Print( "m, r, Q, R: ", m, ", ", r, ", ", Q, ", ", R, ".\n" );
if R=0 then
lst := [0..r-1]*Q;
else
lst := [0..r-1]; # dummy initialisation, only lst[1]=0 is used
lst[r] := m/2 - (Q+1); # we have v_r = m/2 - (m_1-m_0) and m_1-m_0=Q+1
# we have r>0 as r is odd
dinges := Q; # dinges = |m_i-m_{i-1}| = v'_{r-i+2}-v'_{r-i+1}
# with v'_i = v_i if i is even, v_i-m/2 if i is odd
# we count i=1..r here instead of i=0..r-1 as in the paper
for i in [2..r] do
if i = r-R+2 then
dinges := Q+1;
fi;
if i mod 2 = 0 then
lst[r-i+1] := lst[r-i+2]-dinges+m/2;
else
lst[r-i+1] := lst[r-i+2]-dinges-m/2;
fi;
od;
# It will turn out that lst[1] is always 0. But this is a nice check
# on the code!
fi;
return lst;
end;
AdmOddOdd := function( m, r )
# m and r are odd, r <= m
local M,Q,R,i,lst,dinges,
db_m;
M := 2*m;
Q := IntQuo( M/2, r );
R := M/2 mod r;
Print( "M, r, Q, R: ", M, ", ", r, ", ", Q, ", ", R, ".\n" );
if R = 0 then
lst := 2*[0..r-1]*Q; # the "2" will be deleted at the end of this function
else
lst := [0..r-1]; # dummy initialisation, only lst[1]=0 is used
if R mod 2 = 0 then
dinges := Q;
else
dinges := Q-1;
fi;
lst[r] := M/2 - dinges; # we have r>0 as r is odd
db_m := dinges;
Print( "N_0 = ", NormBound( M, r ), ", m_0-N_0 = 0, m_1-N_0 = ", db_m );
for i in [2..r-1] do
# Adapt dinges?
if R mod 4 = r mod 4 then
if i = (r-R)/2+1 then
dinges := Q+1;
fi;
elif R mod 4 = (r+2) mod 4 then
if i = (r-R)/2+2 then
dinges := Q+1;
fi;
elif R mod 4 = 2 then
if i = r - R/2 + 1 then
dinges := Q+2;
fi;
else # R mod 4 = 0
if i = r- R/2 + 2 then
dinges := Q+2;
fi;
fi;
# Compute next entry
if i mod 2 = 0 then
lst[r-i+1] := lst[r-i+2]-dinges+M/2;
db_m := db_m-dinges;
else
lst[r-i+1] := lst[r-i+2]-dinges-M/2;
db_m := db_m+dinges;
fi;
Print( ", m_", i, "-N_0 = ", db_m );
od;
# Compute one-but-last entry.
# Note that the outcome will always be 0! So this is just a sanity check.
if R mod 4 = r mod 4 then
lst[1] := lst[2]-(Q+1)-M/2;
db_m := db_m+(Q+1);
elif R mod 4 = (r+2) mod 4 then
lst[1] := lst[2]-(Q+3)-M/2;
db_m := db_m+(Q+3);
elif R mod 4 = 2 then
lst[1] := lst[2]-(Q+2)-M/2;
db_m := db_m+(Q+2);
else # R mod 4 = 0
lst[1] := lst[2]-(Q+4)-M/2;
db_m := db_m+(Q+4);
fi;
Print( ", m_", r, "-N_0 = ", db_m, ".\n" );
fi;
Print( "Double vector is ", lst, ".\n" );
if not ForAll( lst, i->i mod 2 = 0 ) then
Print( "Something has gone terribly wrong...\n" );
fi;
return lst/2;
end;
AdmissibleVector := function( m, r )
# m and r are positive integers
# Computes an admissible vector of length r and modulus m of maximal norm.
# Here "norm" means Lee norm and "maximal" is as given by the NormBound
# function.
local main, rest, Q, R;
if m mod 2 = 0 and r mod 2 = 0 then
return AdmEvenEven( m, r );
else
if m mod 2 = 1 and r mod 2 = 0 then
main := AdmOddEven( m, r );
else # r is odd
if m mod 2 = 0 then
Q := IntQuo( r, m );
R := r mod m;
if r >= m and R < m then
R := R+m;
Q := Q-1;
fi;
main := Concatenation( List( [1..Q], i->[0..m-1] ) );
rest := AdmEvenOdd( m, R );
Append( main, rest );
else
if r >= m then
main := Concatenation( [0..m-1], AdmOddEven( m, r-m ) );
# The new dimension r-m is even!
# This is done differently in the paper: there, we reduce
# to the case r