Is it ok to mention a research interest with professors outside of your department in a letter of intent?
You don't need to contact the other professors right away, but you could do it now, and at some point before deciding where you're going to go, yes, good idea.

Yes, do check for cross-department affiliation.  Careful with this -- sometimes a department will list Prof. Other-Department on their list of faculty members, but later will hedge that if you try to have Prof. O-D be your official advisor.  If it was just done to inflate your department's faculty list, things could get a little challenging.  This is not necessarily an unresolvable problem, but it could be helpful to ask the department about this sooner rather than later.  Also see if there are one or two faculty members in your target department who could be natural committee members for your thesis committee.

Should you skip all of that and apply to a computer science department instead?  To decide this, consider:


What the PhD exams cover in each department
What teaching assistantships each department has, and what your duties would be
Are there other courses in the target department you'd be interested in taking
Where do you think you'd feel most at home


At the end of this process, you may end up applying for a couple of math or applied math programs and a couple of CS programs.

I looked at your profile and have an additional comment.  A long time ago I was familiar with CS at UW-Madison, which was, and probably still is, strong in theoretical CS, and had lots of TA-ships.  Such a program would have been a reasonable choice, but you would have had to choose one or two additional areas of CS to do an exam in.  That might have been an argument for choosing the math program as your home department.  I'm just mentioning this one as an example of how you might apply the considerations in my proposed list.