Intuitive explanations for the concepts of divisor and genus
Solution 1:
If you want to avoid algebraic geometry and topology, then you will probably be forced to use algebra. This is okay, because the things you ask about have algebraic interpretations.
First of all, it probably helps to write the function field as $k(x,y),$ where $x$ and $y$ are related by some equation $f(x,y) = 0$. One problem is going to be that $f$ can't be chosen to be smooth in general (because not every curve can be embedded as a smooth plane curve), but it's probably best to ignore this; if it becomes important, then probably your colleagues will be delving deeper into the theory anyway, and so the whole level of explanation can be ramped up.
Now to explain divisors, you can have them imagine intersecting $f(x,y) = 0$ with some other curve $g(x,y) = 0$; the intersections will be a bunch of points, possibly with multiplicity. This is a divisor. So divisors are just natural ways of encoding how curves intersect one another. (Again, I am ignoring here the issue of points at infinity; you will have to decide whether that is appropriate, or whether you need a higher level of precision in your explanations.)
As for the genus, it's a little more complicated to explain algebraically, but possible; here goes:
Suppose that the equation $f(x,y) = 0$ has degree $d$, so your function field corresponds to a degree $d$ curve in the plane. Now let $V_n$ be the vector space of all polynomials of degree $\leq n$ in $x$ and $y$. Let's suppose that $n \geq d$ (and in general, we should think that $n$ is large).
A simple computation shows that $V_n$ has dimension $(n+2)(n+1)/2$. Inside $V_n$, we have a subspace consisting of all the multiples of $f$. This subspace is obtained by taking the elements of $V_{n-d}$ (i.e. polynomials of degree at most $n-d$) and multiplying them by $f$, i.e. it is the subspace $f V_{n-d}$ of $V_n$, and so has dimension $(n-d+2)(n-d+1)/2$. If we look at the quotient $V_n/fV_{n-d},$ this then has dimension $n d + 1 - (d-1)(d-2)/2$.
What is the meaning of this quotient?
If $g \in V_n$ represents a non-zero element of $V_n/fV_{n-d}$, then it is a degree $n$ equation that is not divisible by $f$, so it doesn't vanish identically on $f(x,y) = 0$, so by Bezout's theorem, the intersection of $g(x,y) = 0$ and $f(x,y) = 0$ is $n d$ points, i.e. a divisor of degree $n d$. So we see that non-zero elements of $V_n/f V_{n-d}$ correspond to those divisors of degree $n d$ that are obtained by intersecting $f(x,y) = 0$ with a degree $n$ curve. (In fact, we should think about non-zero elements up to scaling, because if we multiply $g$ by a non-zero scalar, the curve $g(x,y) = 0$ doesn't change.)
Thus among all the degree $n d$ divisors on $f(x,y) = 0$, those that come by intersecting with a degree $n$ curve form a space of dimension $n d - (d-1)(d-2)/2.$ (Here I have subtracted 1, because rescaling accounts for 1 of the dimensions in the above formula.)
Now what is the dimension of the space of all divisors of degree $n d$ (with non-negative coefficients, which are the only kind that can possibly arise as intersections; divisors with non-negative coefficients are called effective)? Well, we just have to choose $n d$ points and add them together. We are choosing the points from a curve, which is one-dimensional, so that means there is an $n d$-dimensional space of effective divisors of degree $n d$.
Thus we see that, in the $n d$-dimensional space of all effective divisors of degree $n d$, those that arise by intersecting with a degree $n$ curve are a subspace of dimension $n d -(d-1)(d-2)/2$.
The quantity $(d-1)(d-2)/2$ is precisely the genus. So what we see is that the bigger the genus is, the harder it is for a degree $n d$ divisor on $f(x,y) = 0$ to be obtained by intersecting with another curve.
For example, if the degree $d$ is $1$ or $2$, then the genus vanishes, and
every degree $n d$ divisor comes from intersecting with a degree $n$ curve.
E.g. on a conic (i.e. when $d = 2$) any two points come from intersecting with a line
(the line that passes through those two points), any four points come from intersecting
with a conic, and so on.
On the other hand, if the degree $d = 3$, then not all triples of points on $f(x,y) = 0$ come from intersecting with a line: in fact if you give yourself two points, then they determine a line, which in turn determines the 3rd point of intersection. Similarly (going up to the case $n =3$), a general set of 9 points on the cubic doesn't come from intersecting with another cubic; instead, if you give yourself 8 points on the cubic curve, you can find another cubic passing through these 8 points, and its 9th point of intersection is uniquely determined by the given 8 points. (Since 9 = 8 + 1, this is a particular manifestation of the fact that our cubic curve has genus 1.)
As you can see, I've lapsed into a more geometrical way of thinking (using notions such as dimension), but I don't think one can avoid this completely: the concept of genus arose historically from essentially the kind of computations that I've just been making, and at some point you have to think about spaces of divisors and their dimensions if you want to understand it. Still, I hope that this gives you an avenue to explaining the concept which is more algebraic, and so more accessible to your colleagues.
One more technical remark: The space $V_{n}/f V_{n-d}$ is an example of a Riemann--Roch space, and the formula for its dimension ($n d + 1 - $ the genus) is a special case of the Riemann-Roch formula.
[Technical remark added in response to a question of T. in the comments below; feel free to ignore it if it is at too high a level:] Note that the above discussion works even if $f$ is allowed to be singular (and irreducible, say, so that we can't have polynomials $g$ which vanish on one component of $f(x,y) = 0$ without vanishing on the whole curve). The reason is that $(d-1)(d-2)/2$ is always the arithmetic genus of a plane curve of degree $d$, whether or not the curve is smooth, and it is the arithmetic genus that intervenes in the Riemann--Roch formula. (I believe that this is the origin of the adjective arithmetic in arithmetic genus: it is this version of the genus for singular curves that comes up when you make Riemann--Roch-type calculations of the dimensions of various spaces of divisors.)
Solution 2:
If your CS friends are like me, they might still find the answers above a little overwhelming. So you could start as follows:
First, show them the Wiki's divisor page (it always works!). Then explain to them that by the fundamental theorem of arithmetic, any divisor is just a bunch of prime numbers with multiplicities.
Next, tell them that completely similar to $\mathbb Z$, the FTA works over $\mathbb C[x]$ (which you can think of as a line). Except now that each "divisor" (polynomial) can be thought of as a bunch of points (roots of the polynomial) on that line, with multiplicities.
But why stop as a straight line? One can do the same thing for a (reasonably nice) curve on the plane, and a natural way to get a bunch of points is to intersect with another curve. By the way, a bunch of points "divide" the curve, further justifying the terminology!
Back to $\mathbb C[x]$, you can point out that the total numbers of points (with mult.) is the degree of your polynomial $p(x)$, or the dimension of the vector space $\mathbb C[x]/(p(x))$.
At this point, if they still follow you, show them Matt E's splendid answer (-:
Solution 3:
Charles has already explained the notion of genus (which comes from topology--there's also a purely algebraic notion of genus as a first cohomology group, but I at least would find it less intuitive). So I'll talk about divisors.
First of all, the analytic notion of a nonsingular projective curve is a compact Riemann surface. "Nonsingular" translates to "complex manifold," "curve" translates to "dimension 1," and "projective" translates to "compact." So I will talk about Riemann surfaces.*
If you have a Riemann surface, it's locally the same as the complex plane. And in the complex plane, you have a way to measure the order of the zero of a holomorphic function. More generally, you can measure (in $\mathbb{Z}$) the order of a zero of a meromorphic function (which is negative if it has a pole, zero if it is nonvanishing and analytic, positive if it has a zero). So to any meromorphic function (of course, we don't restrict to holomorphic ones---they're all constant) on a compact Riemann surface, we can assign a finite set of points with multiplicities consisting of the places where the order is nonzero (i.e., the zeros and poles).
A divisor is more general. It's just a formal sum of points on the Riemann surfaces with multiplicities. A divisor may come from a function as above; then it's called principal. In general, however, it does not. Yet given a divisor $D$, we can associate a vector space of meromorphic functions such that $div(f)+ D$ is a divisor with nonnegative coefficients. This is denoted $L(D)$ and its dimension by $l(D)$.
The Riemann-Roch theorem is then a statement about the dimensions $l(D)$. One of its consequences, in particular, is that if $|D|$ (the sum of the multiplicities) is large, then you can always find a (nonzero) element of $L(D)$. This is intuitively easy to understand. If $D$ is large, then you are allowing lots of leeway for $f$, potentially having poles at many places.
*I'm being informal here, but there is a general "GAGA" theory about these equivalences that goes into much more detail, which I know next to nothing about.
Solution 4:
Well, the concepts of genus and divisors come from geometry/topology intuition originally, so those explanations are generally going to be the fastest.
However, we can give very rough versions without needing to say "genus is the number of holes in the surface that the curve looks like." You can think of genus as a measure of how complicated the function field is. Naturally $k(x)$ is going to be the simplest possible one, and it happens to be genus zero. Genus one function fields look like $k(x,y)$ but where $y^2$ is a cubic in $x$. Now, this isn't very precise, but it's a rough thing.
As for divisors, the topology/geometry of them is "linear combinations of points, modulo zero-$\infty$ loci of functions," but to handle it purely algebraically, you'll want to change the word "point" to "discrete valuations", so these are integer linear combinations of the various ways to describe the order of an element of the function field, modulo some set of trivial ones.