Documentation
¶
Overview ¶
Package logderivarg implements log-derivative argument.
The log-derivative argument was described in Haböck22 as an improvement over BCG+18. In BCG+18, it was shown that to show inclusion of a multiset S in T, one can show
∏_{f∈F} (x-f)^count(f, S) == ∏_{s∈S} x-s,
where function `count` counts the number of occurences of f in S. The problem with this approach is the high cost for exponentiating the left-hand side of the equation. However, in Haböck22 it was shown that when avoiding the poles, we can perform the same check for the log-derivative variant of the equation:
∑_{f∈F} count(f,S)/(x-f) == ∑_{s∈S} 1/(x-s).
Additionally, when the entries of both S and T are vectors, then instead we can check random linear combinations. So, when F is a matrix and S is a multiset of its rows, we first generate random linear coefficients (r_1, ..., r_n) and check
∑_{f∈F} count(f,S)/(x-∑_{i∈[n]}r_i*f_i) == ∑_{s∈S} 1/(x-∑_{i∈[n]}r_i*s_i).
This package is a low-level primitive for building more extensive gadgets. It only checks the last equation, but the tables and queries should be built by the users.
NB! The package doesn't check that the entries in table F are unique.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Source Files