MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I hope it's not a trivial question... Suppose I have a finite dimensional vector space $V$ over $\mathbb{Q}$ with a distinguished basis (in my case it's the $k$th graded piece of the free associative algebra on two generators), and a one dimensional affine space

$$S=\lbrace a+\lambda b,\lambda \in \mathbb{Q} \rbrace $$

where $a,b \in V$ are explicitly given. As you may have guessed, $a$ and $b$ are respectively a particular solution of a linear equation and a basis of the kernel of the associated linear map, which were computed using a computer algebra system (SAGE).

Let's call denominator of an element $x$ of $S$ the LCM of all denominators of the coordinates of $x$ expressed in the distinguished basis. The context doesn't really matter, but there is a general result on my particular problem stating that there exists an element of $S$ whose denominator is smaller than a given constant $D$. It turns out that the solution $a$ returned by SAGE match exactly this bound, i.e., its denominator is precisely $D$, which actually I don't find so surprising after all.

But now, of course, I'm curious to know:

  1. if this bound is optimal, i.e., if there exists solution with a smaller denominator
  2. how many such solutions there are, i.e., if this bound on the denominators is sufficient to select a particular (maybe up to some trivial modifications) solution.

So my question can be formulated as follows:

Given two vector $a,b \in \mathbb{Q}^n$, is there an algorithm which can find a $\lambda \in \mathbb{Q}$ such that the denominator of $a+\lambda b$ is minimal ?

Edit: In order to give a motivation to the question: I wrote down a small SAGE program which computed a rational, even, Drinfeld associator (very roughly a formal power serie in two non-commuting variables satisfying some complicated equation) up to and including degree 8. It can be computed recursively by solving linear equations. It turns out that such an element is uniquely determined up to degree 6 (and hence, up to degree 7 because it's even), but in degree 8 the kernel is one dimensional. The result I was mentionning is a paper by Alekseev, Podkopaeva and Severa proving the existence of associators whose denominators satisfies a specific upper bound.

It seems to me that the question is already hard when $n=1$. Still, in my case $n$ is not that big, and even a "brute force" algorithm would be fine. I'm also wondering is there is, at least, an algorithm which can approximate the result (something like LLL does for some minimzation problem in lattices).

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.