Basics for quantum analogs

[ulthiel]

Added basic functions for quantum analogs that I had implemented in my JuLie package: quantum integers, factorials, and binomials. They work also with specializations in any (commutative) ring.

[codecov]

Codecov Report

Attention: Patch coverage is 98.36066% with 1 line in your changes missing coverage. Please review.

Project coverage is 84.05%. Comparing base (e3f1503) to head (bd4d75c).
Report is 2 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #2183      +/-   ##
==========================================
+ Coverage   84.01%   84.05%   +0.04%     
==========================================
  Files         592      593       +1     
  Lines       81674    81733      +59     
==========================================
+ Hits        68617    68700      +83     
+ Misses      13057    13033      -24     

Files	Coverage Δ
experimental/QuantumAnalogs/src/QuantumAnalogs.jl	98.36% <98.36%> (ø)

... and 4 files with indirect coverage changes

[fingolfin]

Thank you, this looks really good!

I still have a bunch of remarks, but most of these are on the cosmetically level, or optional, or both.

[fingolfin]

But quantum_integer(5,1) is not in ℚ(𝐪) ... Also this is quite technical. Can't we just write this:

Suggested change

	Let ``n ∈ ℤ`` and let ``ℚ(𝐪)`` be the fraction field of the polynomial ring ``ℤ[𝐪]`` in
	one variable ``𝐪``. The **quantum integer** ``[n]_𝐪 ∈ ℚ(𝐪)`` of ``n`` is defined as
	For an integer `n` and a ring element `q`, the **quantum integer** ``[n]_q`` is defined as

[fingolfin]

In general I would suggest to minimize the use of Unicode. Most of it seems not necessary here. E.g. why does q have to be in (faux) bold face?

[fingolfin]

For a mathematical text, it is cool to derive these properties and use them to justify the definition. I think this text would fit perfectly into quantum_analogs.md.

But for a docstring, I'd keep it much simpler and to the point, and I would also avoid excessive use of LaTeX and math formulas which are hard to read in a REPL anyway.

So how about just stating the concrete definition, and point to the manual for the justification? E.g. like this

Suggested change

	We have
	```math
	[n]_𝐪 = \sum_{i=0}^{n-1} 𝐪^i ∈ ℤ[𝐪] \quad \text{if } n ≥ 0
	```
	and
	```math
	[n]_𝐪 = -𝐪^{n} [-n]_𝐪 \quad \text{for any } n ∈ ℤ \;,
	```
	hence
	```math
	[n]_𝐪 = - \sum_{i=0}^{-n-1} 𝐪^{n+i} ∈ ℤ[𝐪^{-1}] \quad \text{ if } n < 0 \;.
	```
	``[n]_q = 1 + q + q^2 + ... + q^{n-1}`` if ``n \geq 0`, in particular ``[0]_q = 1``. For negative `n` we use the identity
	```math
	[n]_q = -q^n [-n]_q
	```
	which requires that `q` is invertible, and thus obtain
	```math
	[n]_q = - \sum_{i=0}^{-n-1} q^{n+i} ∈ ℤ[q^{-1}] .
	```

[fingolfin]

All of this sounds OK to me for a description in the reference manual, but isn't it a bit overkill for the docstring? Esp. since it is kinda hard to read this in a terminal?

[fingolfin]

So then it is not type stable.

How about instead negative n leads to an error if q is an integer; if a user wants that, they need to to call e.g. quantum_integer(-5, QQ(3)) ?

But perhaps this case is needed so frequently that the inconvenience outweighs the type instability?

[fingolfin]

Alternative implementation:

Suggested change

	R = parent(q)
	if isone(q)
	return R(n)
	else
	z = zero(R)
	if n >= 0
	for i = 0:n-1
	z += q^i
	end
	else
	for i = 0:-n-1
	z -= q^(n+i)
	end
	end
	return z
	end
	R = parent(q)
	isone(q) && return R(n)
	n >= 0 && return sum(i -> q^i, 0:n-1)
	return -sum(i -> q^(n+i), 0:-n-1)

Of course this leaves potential for optimization, because we compute 1, q, q^2, q^3, ... "naively", i.e. to compute, say, q^40, we don't use that we already computed q^39 before! I am not sure if we already have a function doing that "neatly"

Oh, and if q is an integer, and we care about efficiency, then I think the last line would be better off if it used recursion (i.e.: first sum powers of an integer, then perform a single division at the end; instead of summing powers of a fraction). So:

Suggested change

	R = parent(q)
	if isone(q)
	return R(n)
	else
	z = zero(R)
	if n >= 0
	for i = 0:n-1
	z += q^i
	end
	else
	for i = 0:-n-1
	z -= q^(n+i)
	end
	end
	return z
	end
	R = parent(q)
	isone(q) && return R(n)
	n < 0 && return -q^n * quantum_integer(-n, q)
	return sum(i -> q^i, 0:n-1)

[fingolfin]

Perhaps use \binom, it is standard and the resulting TeX is more readable in the REPL. Also of course my comments from above also apply here (so I'd replace 𝐪 by q)

Suggested change

	``\begin{bmatrix} n \\ k \end{bmatrix}_𝐪 \in ℚ(𝐪)`` is defined as
	``\binom{n}{k}_𝐪 \in ℚ(𝐪)`` is defined as

[fingolfin]

Suggested change

	are only defined for non-negative integers—but the second expression is well-defined for
	are only defined for non-negative integers, but the second expression is well-defined for

[fingolfin]

All of this IMHO belongs into the .md file but not the docstring.

[fingolfin]

This section doesn't really add anything, esp. if the text before it were shortened to just describe what the function does?

Suggested change

	# Functions
	The functions `quantum_binomial` work analogously to [`quantum_integer`](@ref).

[ulthiel]

Thanks, @fingolfin. I had a discussion with @fieker: the function quantum_integer(n) may be problematic as is minimal_polynomial without passing the ring. He also suggested to implement a structure for quantum integers (so, basically the ring of quantum integers). I think this would be the way to go. I never thought about that before. That's why I changed the PR to draft mode.

[thofma]

Just wanted to say that I was in need of quantum binomial coefficients today and the changes here would have come in handy.

[ulthiel]

Just wanted to say that I was in need of quantum binomial coefficients today and the changes here would have come in handy.

Will do the update in the next couple of weeks. (I personally decided against implementing a dedicated ring as mentioned above for now, I hope you didn't need that particular feature...).

[fingolfin]

I've discussed this PR this morning with @ulthiel and based on that I've now rebased it -- doing this I noticed that a bit more work was needed than I expected, and as a result I've now moved it into a new experimental/QuantumAnalogs/ directory. But the final place for this probably should be in src/Combinatorics.

Unfortunately this move resulted in the existing comments on this file to loose their place, i.e. they are no longer attached to the relevant code :-(. Since that was the case now anyway, I've decided to also perform the changes from tabs to spaces (I didn't do those at first in the hopes that the code review comments would stay attached). I also performed some other "obvious" tweaks.

But I did not e.g. touch the unicode, or move anything to the .md file. @ulthiel I am happy to help with that, too, but it's the kind of change I wouldn't want to make w/o coordinating with you.