# $Source: /u/maple/research/lib/LREtools/src/RCS/test_ratsols,v $
# $Notify: mvanhoei@daisy.uwaterloo.ca
#
# Mod p test for the existence of rational solutions.
#
# Calling sequences:
# For a difference operator:    test_ratsols(L,x,tau)
# For a differential operator:  test_ratsols(L,x,DF,true)
#
# Author: Mark van Hoeij, 1998.

# Test for rational solutions modulo a small prime of
# a difference (optional: differential) operator.
# Input: L in C[x,tau]
# Output:  false -> L has no rational solutions in char 0.
#          true  -> L could have rational solutions.
`LREtools/test_ratsols`:=proc(L,x,tau,p,opt)
	local L1,c,b,no,n,A,L2,i,j,D,U;
	# Differential operator?
	option `Copyright (c) 1998 Waterloo Maple Inc. All rights reserved.`;
	D:=evalb(nargs>4 and opt);
	if type(p,list) then # p is a list of primes
		RETURN(p=[] or (procname(L,x,tau,p[1],D)
		 and procname(L,x,tau,p[2..-1],D)))
	fi;
	U:=`if`(D,'dsolve','LREtools');
	userinfo(4,U,`Ratsols test modulo`,p,`start time`,time());
	# Reduce to a finite field. Note that although in
	# principle any L can be reduced modulo any p,
	# ReduceField can not handle all cases; it produces
	# an error message when it can't do the reduction,
	# so we need to traperror that and we simply give
	# up on those cases.
	L1:=traperror(ReduceField(L,{x,tau}) mod p);
	if L1=lasterror or L1=0 then
		return true
	fi;
	no:=proc(a,b,x,p)
		local k,i;
		option `Copyright (c) 1998 Waterloo Maple Inc. All rights reserved.`;
		k:=Expand(Rem(a,b,x) mod p) mod p;
		[seq(coeff(k,x,i),i=0..p-1)]
	end:
for c in [1,2] do
	b:=x^p-`if`(D,0,x)-c;
	L2:=Expand(Rem(L1,b,x) mod p) mod p;
	if L2=0 then next fi;
	n:=degree(L2,tau); # the order of the reduced operator may be
	# smaller than the order of L, but that doesn't matter.
	A:=matrix(p,p,[seq(no(add(coeff(L2,tau,i)*
	 `if`(D,`if`(i=0,x^j,diff(x^j,x$i)),(x+i)^j)
	 ,i=0..n),b,x,p,0),j=0..p-1)]);
	# Note: this is the matrix (modulo the polynomial b) of the
	# action of L on Fp(x) w.r.t the basis [x^0,..,x^(p-1)].
	# It's not the p-curvature matrix, but it serves the
	# same purpose.
	if Expand(Det(A) mod p) mod p <> 0 then
		userinfo(2,U,L,
		 `has no non-zero rational solutions modulo`,p);
		return false
	fi
od;
	# Now we've gained nothing, but didn't lose much time either.
	true
end:

#savelib('`LREtools/test_ratsols`'):