This is a question about recommended style for a paper.

I am able to show an upper bound of the form $f(n) = O(c^n)$. While I have a formula satisfied by $c$, it is a messy formula and I cannot solve it in closed form. I can easily solve this formula numerically, getting a high-precision approximation to $c$. By rounding up I could explicitly get upper bounds $O(c'^n)$ for any $c' > c$.

How should I describe this situation in a paper? Would it be OK to just state that I numerically maximize $c$ and give the decimal approximation? Should I choose a particular value of $c'$ and prove it (by evaluating the expression at $c'$ numerically)?

It feels a little awkward having a theorem in my paper which involves some approximate numerical quantity.

Thanks for any advice

  • 2
    $\begingroup$ I would give an approximation to, say, 3 digits in the abstract and/or introduction. In the actual theorem, I'd give the constant a more unique label than $c$, and precede it by a definition giving the exact formula it satisfies and a note on its numerical approximations. $\endgroup$ – Emil Jeřábek supports Monica Aug 2 '11 at 13:20
  • 3
    $\begingroup$ It is matter of taste. Mine is this: If you think the $c$ you obtained is sharp, state it in full. If the whole point of your result is that the bound is exponential (not doubly exponential say), write it as "c for an absolute constant $c>0$" or give some low-precision approximation (preferably a small integer). If the point of your result is that you improve the value of $c$ someone obtained previously, give numerical approximation (2-3 digits after the first digit improved). $\endgroup$ – Boris Bukh Aug 2 '11 at 13:23
  • 2
    $\begingroup$ Shouldn't this be community wiki? $\endgroup$ – Emil Jeřábek supports Monica Aug 2 '11 at 13:41
  • 1
    $\begingroup$ As an aside, there are situations like $f(n) = 2^n \log n$ where $f(n) = O(c^n)$ for all $c>2$ but not $f(n) = O(2^n)$. $\endgroup$ – Gerald Edgar Aug 2 '11 at 14:26

It seems best to me, from the information you give, to somehow describe the situation in the way you did here.

To be a bit more precise what I mean. You could do something like this.

Theorem: We have $f(n) = O(c^n)$ where $c$ is given as the solution of 'defining equation for $c$'.

Followed by something like:

Note that in particular the above result implies that $f(n)=O(d^n)$ with $d=1.2345$ as, solving the above equation numerically, one can see $c<1.2345$.

One could also do the dual, i.e., give the numerical value in the result and give the explanation how it arises afterwards. However, I would not just mention the 'defining equation' in the proof but close to the fomulation of the result.

Since you are worried about this: it is not that uncommon to have theorems where the constant arises as a numerical approximation to someting 'complicated.'

In case the defining equation is very complicated (and you are worried about too much clutter in the formulation of the theorem) and/or there is something to be discussed regarding existence of solutions or alike, I suggest to define the $c$ outside the formulation of the result.

Now, I said above, I would not hide the defining equation in the proof. However, I would make an exception to this general advice in case it is really complicated or only understandable in the context of the proof. Still, I then would write a sentence pointing to the place in the proof where it arises right after (or possibly even in) the formulation of the theorem.

In any case, what seems important to me is to make clear for the reader how the numerical constant arises.

One additional aspect to keep in mind is the following question: Will, and if so in which form, readers care about the numerical value?

If the point of the paper is that the constant is better than in early work, of course, the value and this fact needs to be more visible, than if this is the first bound of this form and the value of the constant is by and large irrelevant.

  • $\begingroup$ The OP used $O(c^n)$ and not $o(c^n)$. $\endgroup$ – user5810 Aug 2 '11 at 22:43
  • $\begingroup$ Thanks, I corrected this inconsistency, and some other typos. $\endgroup$ – user9072 Aug 3 '11 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.