I use Ubuntu 20.04.6 LTS.
I have downloaded and tested:
audacity-linux-3.5.1-x64.AppImage
audacity-linux-3.6.3-x64.AppImage
audacity-linux-3.7.1-x64-20.04.AppImage
Only 3.5.1 works. The others cannot open. They are not recognized as packages.
Although I do have a Linux computer here around, I cannot at the moment test whether it works here. And “my” Linux isn’t Ubuntu, but Linux Mint “Wilma”.
Could be that the AppImages were damaged during the download - otherwise, we would have read about this problem here before. Did you download from the official site - www.audacityteam.org → Downloads → older versions, which links to Old Audacity versions download ?
However: do you really, really need the latest version of Audacity (means, features which were introduced with version 3.6 / 3.7 and missing before)? If not, just continue with the version which works. My “music Mac” (macOS 10.13.6 “High Sierra”) still works with version 2.4.2, which does everything I need. My other Mac with macOS 15.2 “Sequoia” has Audacity 3.6.1 installed.
I download from Audacity ® | Download for Linux
I just tried again (audacity-linux-3.7.1-x64-20.04.AppImage), with same result. (The file is identical.)
And I just tried downloading it with Chromium (instead of Firefox). Same result.
The older versions were downloaded when they were the current version.
I just found a workaround for the missing horizontal scroll bar in audacity-linux-3.5.1-x64.AppImage - Missing horizontal scroll bar - so I don’t NEED a newer version. 
Ensure that the AppImage file has “execute” permissions.
Yes!
I always overlook permissions.
Enabling execute permission for audacity-linux-3.7.1-x64-22.04.AppImage makes it work. Strangely audacity-linux-3.7.1-x64-20.04.AppImage still does not work, although I am running Ubuntu 20.04.6 LTS.
Edition / addition:
I forgot to mention that the ‘20.04’ version no longer gives an error, but it doesn’t open.