vv

11977 Reputation

19 Badges

7 years, 256 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]

(1)

eliminate(sys, [x,y]);

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

(2)

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,

 

eval(sys,[a=1,b=3,c=2]);

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

(3)

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

[0, 0, 0]

(4)

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]]

 

1

(5)

Now, the correct result (also by hand):

solve(sys[[1,2]], {x,y});
eval(sys[3],%);
numer(simplify(%));

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

 

c/(a-b)-2*a/(a-b)

 

c-2*a

(6)

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]

(7)

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

[2*a-c]

(8)

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]

(9)

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

s:="România":
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.

restart
f:= t -> abs(GAMMA(2*t+I)):  # We want D(f)(1)
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; 
eval(%,t=1);
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

   

       0.8772316598
       0.8772316599

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.

restart
`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) )
end:
f:= t -> abs(GAMMA(2*t+I));
D(f)(1); evalf(%);   # OK now

               

         0.8772316597

Now diff works too.

diff(f(t),t);
eval(%,t=1);
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);

       508536

 

A2.  Let k be a nonnegative integer.  Evaluate  

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

        4^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; 

        1990

 

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.

restart;
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'):
Digits:=500:
for n in numer~(L[3..]) do
  if not evalf(ceil(a)=floor(b)) then printf("n=%d\n", n) fi;
od:

n=777451915729368
n=140894092055857794
n=1526223088619171207
n=54545811706258836911039145
n=624965662836733496131286135873807507
n=1667672249427111806462471627630318921648499
n=36465374036664559522628534720215805439659141
n=2424113537313479652351566323080535902276508627
n=123447463532804139472316739803506251988903644272
n=97841697218028095572510076719589816668243339678931971
n=5630139432241886550932967438485653485900841911029964871
n=678285039039320287244063811222441860326049085269592368999
n=312248823968901304612135523777926467950572570270886324722782642817828920779530446911
n=5126378297284476009502432193466392279080801593096986305822277185206388903158084832387
n=1868266384496708840693682923003493054768730136715216748598418855972395912786276854715767
n=726011811269636138610858097839553470902342131901683076550627061487326331082639308139922553824778693815

 

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