Criteria for the numerical constant recognition. Odrzywolek, A. arXiv:2002.12690 [cs, stat], February, 2020. arXiv: 2002.12690
Criteria for the numerical constant recognition [link]Paper  abstract   bibtex   
The need for recognition of numerical (decimal, floating-point) constants in terms of elementary functions emerges in many areas of experimental mathematics, numerical analysis, computer algebra systems, model building, approximation and data compression. However, existing solutions are plagued by lack of any criteria distinguishing between random formula, matching literally decimal expansion (i.e. approximation) and probable "exact" (or at least probable) expression match in the sense of Occam's razor. In particular, convincing STOP criteria for search were never developed. In article, such a criteria, working in statistical sense, are provided. Recognition process can be viewed as (1) enumeration of all formulas in order of increasing Kolmogorov complexity (2) random process with appropriate statistical distribution (3) compression of a decimal string. All three approaches are remarkably consistent, and provide essentially the same limit for practical depth of search. Tested unique formulas count must not exceed 1/sigma, where sigma is relative numerical error of the target constant. Beyond that, further search is pointless, because, in the view of approach (1), number of equivalent expressions within error bounds grows exponentially; in view of (2), probability of random match approaches 1; in view of (3) compression ratio much smaller than 1.
@article{odrzywolek_criteria_2020,
	title = {Criteria for the numerical constant recognition},
	url = {http://arxiv.org/abs/2002.12690},
	abstract = {The need for recognition of numerical (decimal, floating-point) constants in terms of elementary functions emerges in many areas of experimental mathematics, numerical analysis, computer algebra systems, model building, approximation and data compression. However, existing solutions are plagued by lack of any criteria distinguishing between random formula, matching literally decimal expansion (i.e. approximation) and probable "exact" (or at least probable) expression match in the sense of Occam's razor. In particular, convincing STOP criteria for search were never developed. In article, such a criteria, working in statistical sense, are provided. Recognition process can be viewed as (1) enumeration of all formulas in order of increasing Kolmogorov complexity (2) random process with appropriate statistical distribution (3) compression of a decimal string. All three approaches are remarkably consistent, and provide essentially the same limit for practical depth of search. Tested unique formulas count must not exceed 1/sigma, where sigma is relative numerical error of the target constant. Beyond that, further search is pointless, because, in the view of approach (1), number of equivalent expressions within error bounds grows exponentially; in view of (2), probability of random match approaches 1; in view of (3) compression ratio much smaller than 1.},
	urldate = {2020-03-07},
	journal = {arXiv:2002.12690 [cs, stat]},
	author = {Odrzywolek, Andrzej},
	month = feb,
	year = {2020},
	note = {arXiv: 2002.12690},
	keywords = {Computer Science - Discrete Mathematics, Computer Science - Symbolic Computation, F.1.m, F.2.3, G.1.m, G.2.3, G.3, G.4, I.1.1, I.2.m, Statistics - Other Statistics},
}
Downloads: 0