11265 Reputation

19 Badges

6 years, 278 days

MaplePrimes Activity

These are Posts that have been published by vv

About eliminate(...)


This post is motivated by a recent answer where I needed a necessary and sufficient condition for three straight lines in space be concurrent. I had to use determinants because the eliminate command did not provide the correct answer.
Investigating the cause, I saw that eliminate uses an heuristic algorithm, instead of using Groebner bases (when possible).

Here is an example.

We want to eliminate the unknowns x an y in the system

a*x + y = 0,  b*x+y+1 = 0, c*x+2*y = 0


sys:=[a*x + y, b*x + y + 1, c*x + 2*y];

[a*x+y, b*x+y+1, c*x+2*y]


eliminate(sys, [x,y]);

[{x = 0, y = 0}, {1}]


So, apparently, the elimination is not possible, i.e. for each triple (a,b,c), the system in x and y is incompatible.
This is not true. For example,



[x+y, 3*x+y+1, 2*x+2*y]


eval(%, [x=-1/2, y=1/2]);

[0, 0, 0]


eliminate  obtained its result this way (just like a superficial human):

solve(sys[[1,3]], [x,y]);
eval(sys[2],%[]); # The result obtained by eliminate

[[x = 0, y = 0]]




Now, the correct result (also by hand):

solve(sys[[1,2]], {x,y});

{x = 1/(a-b), y = -a/(a-b)}






So, for c = 2*a  (and a <> b)  the system in x,y  is compatible.


This result can be obtained with Groebner bases.

Groebner:-Basis(sys, plex(x,y,a,b,c));

[2*a-c, 2*b*y-c*y-c, c*x+2*y, b*x+y+1]


remove(has, %, {x,y});



Note that it is more efficient to use lexdeg([x,y], [a,b,c])  instead of plex(x,y,a,b,c).

Groebner:-Basis(sys, lexdeg([x,y], [a,b,c]));

[2*a-c, 2*b*y-c*y-c, c*x+2*y, b*x+y+1]


The conclusion is that eliminate should use internally Groebner:-Basis for polynomial systems.
Until then, we can use it ourselves!


Maple strings contain extended ASCII characters (codes 1..255). 
The international characters such as  î, ș, Å, Ø ,Ă, Æ, Ç are multi-byte encoded. They are ignored by the Maple engine but are known to the user interface which uses the UTF-8 encoding.
The package StringTools does not support this encoding. However it is not difficult to manage these characters using Python commands (included in the Maple distribution now).
Here are the UTF-8 versions of the Maple procedures length and substring.
You may want to improve these procedures, or to add new ones (my knowledge of Python is very limited).

LEN:=proc(s::string) Python:-EvalFunction("len",s) end proc:

SS:=proc(s::string, mn::{integer, range(({integer,identical()}))})
  local m,n;
  if type(mn,integer) then m,n := mn$2 else m:=lhs(mn); n:=rhs(mn) fi; 
  if m=NULL then m:=1 fi; if n=NULL then n:=-1 fi;
  if n=-1 then n:=LEN(s) elif n<0 then n:=n+1 fi;
  if m=-1 then m:=LEN(s) elif m<0 then m:=m+1 fi;
  Python:-EvalString(cat("\"",  s, "\"", "[", m-1, ":", n, "]"  ));
end proc:

LEN("Canada"), length("Canada");
                              6, 6

LEN(s), length(s);
                              7, 8

SS(s, 1..), SS(s, 1..-3), SS(s, 1..1), SS(s, -7..2), SS(s,1), SS(s,-1); 
            "România", "Român", "R", "Ro", "R", "a"

diff(abs(z), z)  returns abs(1, z)  and the latter, for a numeric z, is defined only for a nonzero real z.
However,  functions such as abs(I+sin(t)) are (real) differentiable for a real t and diff should work. It usually does, but not always.

f:= t -> abs(GAMMA(2*t+I)):  # We want D(f)(1)
evalf(%);  # Error, (in simpl/abs) abs is not differentiable at non-real arguments
D(f)(1); simplify(%); 
evalf(%);   # 0.3808979508 + 1.161104935*I,  wrong

The same wrong results are obtained with diff instead of D

diff(f(t),t):   # or  diff(f(t),t) assuming t::real; 
simplify(%); evalf(%);   # wrong, should be real

To obtain the correct result, we could use the definition of the derivative:

limit((f(t)-f(1))/(t-1), t=1); evalf(%); # OK 
fdiff(f(t), t=1);    # numeric, OK



Note that abs(1, GAMMA(2 + I)); returns 1; this is also wrong, it should produce an error because  GAMMA(2+I) is not real;

Let's redefine now `diff/abs`  and redo the computations.

`diff/abs` := proc(u, z)   # implements d/dx |f(x+i*y|) when f is analytic and f(...)<>0
local u1:=diff(u,z);
1/abs(u)*( Re(u)*Re(u1) + Im(u)*Im(u1) )
f:= t -> abs(GAMMA(2*t+I));
D(f)(1); evalf(%);   # OK now



Now diff works too.

simplify(%); evalf(%);   # it works

This is a probably a very old bug which may make diff(u,x)  fail for expressions having subespressions abs(...) depending on x.

However it works  using assuming x::real, but only if evalc simplifies u.
The problem is actually more serious because diff/ for Re, Im, conjugate should be revized too. Plus some other related things. 

The Putnam 2020 Competition (the 81st) was postponed to February 20, 2021 due to the COVID-19 pandemic, and held in an unofficial mode with no prizes or official results.

Four of the problems have surprisingly short Maple solutions.
Here they are.

A1.  How many positive integers N satisfy all of the following three conditions?
(i) N is divisible by 2020.
(ii) N has at most 2020 decimal digits.
(iii) The decimal digits of N are a string of consecutive ones followed by a string of consecutive zeros.

add(add(`if`( (10&^m-1)*10&^(n-m) mod 2020 = 0, 1, 0), 
n=m+1..2020), m=1..2020);



A2.  Let k be a nonnegative integer.  Evaluate  

sum(2^(k-j)*binomial(k+j,j), j=0..k);



A3.  Let a(0) = π/2, and let a(n) = sin(a(n-1)) for n ≥ 1. 
Determine whether the series   converges.

asympt('rsolve'({a(n) = sin(a(n-1)),a(0)=Pi/2}, a(n)), n, 4);


a(n) ^2 being equivalent to 3/n,  the series diverges.


B1.  For a positive integer n, define d(n) to be the sum of the digits of n when written in binary
 (for example, d(13) = 1+1+0+1 = 3). 

Let   S =  
Determine S modulo 2020.

d := n -> add(convert(n, base,2)):
add( (-1)^d(k) * k^3, k=1..2020 ) mod 2020; 



Here is a very nice (but not easy) elementary problem.
The equality
ceil(2/(2^(1/n)-1)) = floor(2*n/ln(2));


is not an identity, it does not hold for each positive integer n.
How to find such a number?

[This is a re-post, because the original vanished when trying a conversion Question-->Post]

The problem appears in the recent book:
Richard P. Stanley - Conversational Problem Solving. AMS, 2020. 

The problem is related to a n-dimensional tic-tac-toe game. The first counterexample (2000) was wrong due to a multiprecision arithmetic error.
The  author of the book writes 
"To my knowledge, only eight values of n are known for which the equation fails,
and it is not known whether there are infinitely many such values",

but using Maple it will be easy to find more.

A brute-force solution is problematic because the smallest counterexample is > 7*10^14.

a := 2/(2^(1/n)-1): b := 2*n/ln(2):
asympt(b-a, n);


It results:  b - a → 1 (for n →oo);
So, to have a counterexample, b must be close to an integer
m ≈ 2*n/ln(2)  ==> n/m ≈ ln(2)/2

The candidates for n/m will be obviously the convergents of the continued fraction of the irrational number ln(2)/2.

convert(ln(2)/2, confrac, 200, 'L'):
for n in numer~(L[3..]) do
  if not evalf(ceil(a)=floor(b)) then printf("n=%d\n", n) fi;



So, we have obtained 16 counterexamples. The question whether there are an infinity of such n's remains open.


1 2 3 4 5 6 Page 1 of 6