9
$\begingroup$

An arithmetic formula is a well-formed expression involving only the constant 1, and the binary operations of addition and multiplication, with multiplication by 1 not allowed. For instance, $1 + (1 + 1) \times ((1 + 1) + 1)$ is an arithmetic formula. Two quantities are are associated to each arithmetic formula: its value which is just the number obtained when the operations are performed (in the previous example, the value is $7$), and its complexity which is the number of $1$'s appearing in the expression (in the previous example, the complexity is $6$).

The minimal complexity $c(n)$ of an arithmetic formula with value $n$ (also called arithmetic complexity of $n$) has been popularized in [1]. It is not difficult to prove that $$\frac{3}{\log 3} \leq \frac{c(n)}{\log n} \leq \frac{3}{\log 2}, \quad n > 1$$ and slightly better bounds are known, but the precise behaviour of $c(n) / \log n$ is still a mystery (see, for example, [2]).

On the other hand, in [3] it is proved that the number $f(n)$ of arithmetic formulas with value $n$ satisfies $$f(n) \sim C \cdot \frac{\rho^n}{n^{3/2}}, \quad n \to +\infty$$ for some constants $C = 0.145\!\ldots$ and $\rho = 4.076\!\ldots$

Here come my question: Can we obtain some (interesting) statistical results on arithmetic formulas involving both their complexities and their values?

For example (in order of presumed difficulty):

  • What is the asymptotic for the average value of an arithmetic formula of complexity $c$, as $c \to +\infty$ ?

  • What is the asymptotic for the average complexity of an arithmetic formula of value $n$, as $n \to +\infty$ ?

  • If $V_c$ is the random variable representing the value of a random arithmetic formula of complexity $c$, picked with uniform distribution, does some normalization of $V_c$ approach a continuous distribution?

  • If $C_n$ is the random variable representing the complexity of a random arithmetic formula of value $n$, picked with uniform distribution, does some normalization of $C_n$ approach a continuous distribution?

Thank you for any suggestion/reference.

[1] R. K. Guy, Some Suspiciously Simple Sequences, The American Mathematical Monthly, 93 (1986), 186-190.

[2] H. Altman, Integer complexity and well-ordering, Michigan Mathematical Journal, 64 (2015), 509-538.

[3] E. K. Gnang, M. Radziwiłł, C. Sanna, Counting arithmetic formulas, European Journal of Combinatorics, 47 (2015) 40-53.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The second point needs refinement, as 1=1*1=1*1*1=1*1*1*1=... You may need to talk about a weighted distribution of the set having value n. Gerhard "Such As A Finite Cutoff" Paseman, 2017.09.14. $\endgroup$
    – Gerhard Paseman
    Sep 14, 2017 at 14:54
  • $\begingroup$ For the third point, a complexity c formula has a value at most 3^(c/3) or something near that, while the second largest is 8/9 of that at best, and the third largest less than an absolute fraction of the second. How do you handle these outliers in a continuous fashion? Gerhard "Wants To Learn Distributional Thinking" Paseman, 2017.09.14. $\endgroup$
    – Gerhard Paseman
    Sep 14, 2017 at 14:59
  • $\begingroup$ @Gerhard: OP prohibits multiplication by 1 (and there were no edits) $\endgroup$
    – Ilya Bogdanov
    Sep 14, 2017 at 16:00
  • $\begingroup$ @GerhardPaseman I don't get what you're saying about $V_c$. Of course the discribution of $V_c$ is discrete, but maybe some normalization of $V_c$ (like $V_c / 2^c$ or similar) tends to a continuous distribution as $c \to +\infty$. $\endgroup$
    – user40023
    Sep 14, 2017 at 16:23
  • $\begingroup$ Sorry about missing the restriction on multiplication: it changes some ideas I had about using expected values. For the third point, look at the set S_8 of values involving complexity 8. It has 27 as its largest value, and the next largest is 24 followed by 18. I think these ratios persist for all complexities larger than 8 among the largest values. How are you smoothing things to work these values into a continuous distribution of values? Gerhard "One Is The Loneliest Multiplicand" Paseman, 2017.09.14. $\endgroup$
    – Gerhard Paseman
    Sep 14, 2017 at 16:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.