Opened 6 years ago

Closed 5 years ago

# implement gcd(a,b,hold=True)

Reported by: Owned by: rws major sage-duplicate/invalid/wontfix symbolics kbaut N/A todo

The implemented behaviour of `gcd` is consistent if its arguments are rational numbers or polynomials. Trying to give a symbolic variable will convert to polynomial which behaves unexpectedly:

```sage: x=var('x')
sage: gcd(x,4)
1
```

The natural way to handle it is using the keyword `hold`:

```sage: gcd(x,4,hold=True)
---------------------------------------------------------------------------
Traceback (most recent call last)
...
TypeError: gcd() takes no keyword arguments
```

As comment:18 shows this may not be easy and involve other changes.

### comment:1 Changed 6 years ago by kcrisman

One could argue this is (currently) user error, but this would be a great enhancement.

### comment:3 Changed 6 years ago by kbaut

• Stopgaps set to todo

Here's another example, which seems to put this in the "mathematically wrong answer" category:

```sage: sum(gcd(x, 4), x, 1, 4)
4
```

```sage: [gcd(x, 4) for x in range(1, 5)]
[1, 2, 1, 4]
sage: sum(gcd(x, 4) for x in range(1, 5))
8
```

### comment:4 follow-up: ↓ 8 Changed 6 years ago by kcrisman

I think the problem is that while we do get the "right" thing when two polynomials are involved, we somehow don't for a polynomial and an integer, and this isn't well documented. I agree that the end user may not care and that we should find a way to fix it (or at least to raise an error when a symbolic thing shows up in it). This won't be completely trivial, though.

### comment:5 follow-up: ↓ 7 Changed 6 years ago by kcrisman

```        <type 'sage.rings.integer.Integer'>

TESTS:

The following shows that indeed coercion takes place before computing
the gcd. This behaviour was introduced in trac ticket #10771::

sage: R.<x>=QQ[]
sage: S.<x>=ZZ[]
sage: p = S.random_element()
sage: q = R.random_element()
sage: parent(gcd(1/p,q))
Fraction Field of Univariate Polynomial Ring in x over Rational Field
sage: parent(gcd([1/p,q]))
Fraction Field of Univariate Polynomial Ring in x over Rational Field
```

and indeed

```sage: parent(gcd(x,1))
Symbolic Ring
```

So in the symbolic ring this IS the gcd. Hmm. And if you think of this as a polynomial, it makes sense.

So I'm not sure what to say here. The `4` might be a red herring in this case, because we consider `SR` or whatever as more about polynomials over a field, so the gcd is automatically one - maybe? Also check out `x.gcd??`. Just raising questions about what the "right" thing to do is.

```    Make sure we try QQ and not merely ZZ (:trac:`13014`)::

sage: bool(gcd(2/5, 3/7) == gcd(SR(2/5), SR(3/7)))
True
```

### comment:6 Changed 6 years ago by rws

• Description modified (diff)

### comment:7 in reply to: ↑ 5 Changed 6 years ago by rws

• Description modified (diff)

I agree that all examples you give are consistent *if the `gcd` is considered not as a symbolic function. It may simply need an implementation of `hold=True` to allow that usage. The only problem then that I see is that people would have to learn the distinction between an operation and a symbolic function, which they have to in many places anyway.

So just make sure a big NOTE is given in the documentation.

### comment:8 in reply to: ↑ 4 ; follow-ups: ↓ 9 ↓ 10 Changed 6 years ago by kbaut

Are there any problematic cases that don't involve the `sum` function?

I'm wondering if the implementation of `sum` is actually the issue. `sum(expression, v, a, b)` evaluates the expression before substituting values for the variable, unlike `sum(expression for v in range(a, b+1))`. Should they be equivalent?

### comment:9 in reply to: ↑ 8 Changed 6 years ago by nbruin

I'm wondering if the implementation of `sum` is actually the issue. `sum(expression, v, a, b)` evaluates the expression before substituting values for the variable, unlike `sum(expression for v in range(a, b+1))`. Should they be equivalent?

That they are different is a rather fundamental python language feature. Making the two behave equivalently would require rather major surgery on the python parser or some nasty trickery in preparsing.

### comment:10 in reply to: ↑ 8 Changed 6 years ago by rws

Are there any problematic cases that don't involve the `sum` function?

```sage: f(x)=gcd(x,4)/gcd(x,8)
sage: [f(x) for x in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
```

### comment:11 Changed 6 years ago by nbruin

You'd first need to decide what "gcd(A,B)" of two symbolic expressions is:

• if it's "integer" gcd then it can be evaluated for integers entries, it's an error if you feed it something else ostensibly numeric, and it can be left unevaluated if there are variables in there.
• if it's (univariate) polynomial gcd, there needs to be some heuristic to choose the variable wrt. which it would be the gcd (or better, this variable would be part of the input). Anything else would be considered an (invertible) coefficient. This would never be left unevaluated. This is close to what we have now.

We have too little information to define gcd on SR properly. Currently even this doesn't work:

```gcd(x,sqrt(2)*x)
```

The gcd we are currently interfacing with is:

```x.gcd
```

which is limited to polynomials over QQ, but at least it fixes the choice: it's polynomial gcd. That means `gcd(x,4)` should indeed be `1` (or at least a constant).

In any setting, gcd tends to be not stable under evaluation, meaning that if

```G(x) = gcd (a(x),b(x))
```

then for a specialization `x0` of x, one can easily have that `gcd(a(x0),b(x0)) != G(x0)`. That means a "symbolic" gcd will always be problematic.

### comment:12 follow-up: ↓ 14 Changed 6 years ago by rws

That may be, but it presupposes that evaluation is demanded in `SR`. It does not touch my simple wish to hold off evaluation for some time, after which I will gladly use the evaluation already implemented.

So, what arguments against `hold=True`?

### comment:13 Changed 6 years ago by rws

• Summary changed from symbolic gcd() to implement gcd(a,b,hold=True)

### comment:14 in reply to: ↑ 12 ; follow-up: ↓ 18 Changed 6 years ago by nbruin

So, what arguments against `hold=True`?

How do you control when `hold=True` is triggered to be expanded? In particular, in

```sum( gcd( x^2+n,x,hold=True),n,-2,2,hold=True )
```

what do you do to clear to "unhold" the expression and how do you control the order in which that happens? In particular, for your application, you'd need the values of `n` to be substituted before the hold on `gcd` is cleared.

### comment:15 Changed 6 years ago by rws

I see. But then the only reasonable way to achieve it is with different gcd functions, so one can sort out when to hold, i.e., the rational constant version would do it when an expression appeared as argument.

### comment:16 Changed 6 years ago by rws

There are more than one solution to represent the function `gcd(a,n), a in QQ, n in ZZ`. It is always a C-Finite sequence, so reviewing #15714 would help too.

### comment:17 Changed 6 years ago by rws

• Description modified (diff)
• Type changed from defect to enhancement

### comment:18 in reply to: ↑ 14 ; follow-up: ↓ 19 Changed 6 years ago by rws

How do you control when `hold=True` is triggered to be expanded? In particular, in

```sum( gcd( x^2+n,x,hold=True),n,-2,2,hold=True )
```

what do you do to clear to "unhold" the expression and how do you control the order in which that happens? In particular, for your application, you'd need the values of `n` to be substituted before the hold on `gcd` is cleared.

I do not understand. In what way is this different from

```sum(sin(n*pi,hold=True),n,1,5,hold=True)
...
TypeError: symbolic_sum() got an unexpected keyword argument 'hold'
```

which simply does not work, and from which one usually comes to this:

```sage: sum(sin(n*pi,hold=True) for n in range(1,6))
sin(pi) + sin(5*pi) + sin(4*pi) + sin(3*pi) + sin(2*pi)
```

### comment:19 in reply to: ↑ 18 Changed 6 years ago by nbruin

I do not understand. In what way is this different from

```sum(sin(n*pi,hold=True),n,1,5,hold=True)
...
TypeError: symbolic_sum() got an unexpected keyword argument 'hold'
```

which simply does not work, and from which one usually comes to this:

```sage: sum(sin(n*pi,hold=True) for n in range(1,6))
sin(pi) + sin(5*pi) + sin(4*pi) + sin(3*pi) + sin(2*pi)
```

The problem is that "hold" semantics aren't well-defined, so you'd better make sure that for "held" expressions, the answers aren't wildly different depending on when the "hold" is lifted. Never mind that "hold" isn't implemented for sums. You can usually get an implicit hold by doing something like

```f(N)=sum(...,n,1,N)
```

and with that transform you see that your suggested iterator expression is NOT the same:

```sage: var("t,T")
(t, T)
sage: sum(sin(t*pi,hold=True),t,1,T)
0
```

The hold apparently gets lifted by "sum" already (because our "hold" doesn't get translated to maxima, perhaps because a corresponding notion doesn't exist for sine there) and apparently, sum simplifies the expression under the assumption that t is an integer.

That's why I think "hold" is not an appropriate mechanism for a wildly non-continuous function such as "gcd". It's meant to be a manipulation on (polynomial) expressions, not a symbolic function. I don't think SR is equipped to handle operations like that "symbolically".

I know systems like maple and mathematica tend to not make a distinction between "operations" and "symbolic expressions", allowing deferred evaluation on pretty much anything, and in my experience predictability and debuggability of code suffers from it.

Nothing prevents you from defining `function("completely_inert_gcd")` and writing expressions with that. The problem arises when you start trying to use simplification/evaluation rules on this expression. Normally, you'd from the inside to the outside; for your sum example you'd need it from the outside to the inside. We can't really have both if we don't have a way to indicate which method to use where.

### comment:20 Changed 6 years ago by rws

• Milestone changed from sage-6.3 to sage-duplicate/invalid/wontfix
• Status changed from new to needs_review

So, summarily, `gcd` itself has nothing to enhance in this direction, and this ticket should not be stretched to implement something only marginally useful.

### comment:21 Changed 5 years ago by saraedum

• Status changed from needs_review to positive_review

I believe that this should be "positive review". It was set to invalid 20 months ago and nobody complained so it can probably go away.

### comment:22 Changed 5 years ago by vbraun

• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.